Le operazioni regolari dei linguaggi
Le operazioni regolari nei linguaggi formali e nella teoria degli automi sono strumenti fondamentali per manipolare e descrivere insiemi di stringhe.
Le principali operazioni regolari includono:
Unione
L'unione di due linguaggi \( L_1 \) e \( L_2 \), denotata \( L_1 \cup L_2 \), è l'insieme di tutte le stringhe che appartengono a \( L_1 \), a \( L_2 \), o a entrambi.
Esempio. In termini pratici, se \( L_1 = \{a, b\} \) e \( L_2 = \{b, c\} \), allora \( L_1 \cup L_2 = \{a, b, c\} \).
Concatenazione
La concatenazione di due linguaggi \( L_1 \) e \( L_2 \), denotata \( L_1 \cdot L_2 \) o semplicemente \( L_1L_2 \), è l'insieme delle stringhe formate concatenando ogni stringa di \( L_1 \) con ogni stringa di \( L_2 \).
Esempio. Se \( L_1 = \{a, b\} \) e \( L_2 = \{c, d\} \), allora \( L_1 \cdot L_2 = \{ac, ad, bc, bd\} \).
Chiusura di Kleene (Kleene Star)
La chiusura di Kleene di un linguaggio \( L \), denotata \( L^* \), è l'insieme di tutte le possibili concatenazioni di zero o più stringhe di \( L \).
Esempio. Per esempio, se \( L = \{a\} \), allora \( L^* = \{\epsilon, a, aa, aaa, \ldots\} \), dove \( \epsilon \) rappresenta la stringa vuota.
L'operazione "star" si distinghe dalle altre perché è un'operazione unaria. L'unione, l'intersezione, la concatenazione e il complemento sono, invece, operazioni binarie.
Intersezione
L'intersezione di due linguaggi \( L_1 \) e \( L_2 \), denotata \( L_1 \cap L_2 \), è l'insieme delle stringhe che appartengono sia a \( L_1 \) che a \( L_2 \).
Esempio. Se \( L_1 = \{a, b, c\} \) e \( L_2 = \{b, c, d\} \), allora \( L_1 \cap L_2 = \{b, c\} \).
Complemento
Il complemento di un linguaggio \( L \) rispetto a un alfabeto \( \Sigma \), denotato \( \overline{L} \), è l'insieme di tutte le stringhe sull'alfabeto \( \Sigma \) che non appartengono a \( L \).
Esempio. Se \( \Sigma = \{a, b\} \) e \( L = \{a\} \), allora \( \overline{L} = \{b, aa, ab, ba, bb, \ldots\} \).
Queste operazioni sono essenziali per la costruzione e l'analisi di linguaggi formali, automi e grammatiche.
Sono fondamentali in molte aree della computer science, come la compilazione e la progettazione di linguaggi di programmazione.
La chiusura delle operazioni regolari
Le operazioni regolari sui linguaggi formali sono chiuse, il che significa che l'applicazione di queste operazioni su linguaggi regolari produce sempre un linguaggio regolare.
Ad esempio, l'unione di due linguaggi regolari \( L_1 \) e \( L_2 \) è sempre un linguaggio regolare. Se \( L_1 \) e \( L_2 \) sono riconosciuti rispettivamente dagli automi \( A_1 \) e \( A_2 \), possiamo costruire un automa che riconosce \( L_1 \cup L_2 \) utilizzando l'automa a stati finiti non deterministico (NFA) o costruendo un nuovo automa che combina gli stati di \( A_1 \) e \( A_2 \). Ad esempio, se abbiamo due linguaggi regolari \( L_1 = \{a, b\} \) e \( L_2 = \{b, c\} \). L'unione \( L_1 \cup L_2 = \{a, b, c\} \). Lo stesso accade per le altre operazioni.
Tuttavia, non tutti gli automi a stati finiti sono in grado di leggere il risultato di un'operazione regolare.
Un automa finito deterministico non è in grado di leggere la concatenazione di due linguaggi, perché non saprebbe quando finisce la stringa da far analizzare al primo automa $ A_1 $ e quando comincia la seconda stringa da far leggere al secondo automa $ A_2 $.
Ad esempio, se abbiamo due linguaggi regolari \( L_1 = \{a, b\} \) e \( L_2 = \{b, c\} \) la concatenazione delle stringa w1="ab" di L1 con la stringa w2="b" di L2 genera una stringa w1w2="abb" in un nuovo linguaggio regolare. Quando finisce la prima stringa da far elaborare al primo automa? La stringa "abb" potrebbe essere la concatenazione di "ab"·"b" ma anche di "a"·"bb". L'automa deterministico non saprebbe decidere quale parte della stringa far elaborare all'automa $ A_1 $ e quale all'automa $ A_2 $
Questo richiede una costruzione specifica dell'automa risultante, non una semplice combinazione dei due automi originali.
L'idea è di costruire un nuovo DFA che "simuli" il processo di concatenazione. Ad esempio, si potrebbe realizzare una struttura dati basata sulla coppia di stringhe (w1,w2) anziché una concatenazione w1w2.
In alternativa, si può ricorrere a un automa non deterministico.
