Linguaggi regolari
I linguaggi regolari sono una classe di linguaggi formali espressi utilizzando espressioni regolari che possono essere riconosciuti da un automa a stati finiti.
Questi linguaggi prendono il loro nome dalla loro capacità di essere descritti tramite espressioni regolari e costituiscono la classe più semplice e fondamentale nello studio della teoria dei linguaggi formali e degli automi.
Automa a stati finiti
Un automa a stati finiti (AFS) è un modello matematico composto da un insieme finito di stati, uno stato iniziale, uno o più stati finali (di accettazione), un insieme finito di simboli (l'alfabeto) e una funzione di transizione che determina il passaggio da uno stato all'altro in base all'input.
Esempio. Immaginiamo un automa che riconosce stringhe composte da un numero pari di zeri. Questo automa avrà due stati: uno stato iniziale (S0) che rappresenta un numero pari di zeri e uno stato (S1) che rappresenta un numero dispari di zeri. La transizione tra gli stati avviene ogni volta che si legge uno zero: da S0 a S1 e viceversa.
Le espressioni regolari
Un'espressione regolare è una notazione per descrivere e rappresentare insiemi di stringhe all'interno di un linguaggio, tramite delle formule matematiche, in maniera compatta e comprensibile
Le espressioni regolari usano simboli e operatori come concatenazione, unione (alternanza), e chiusura (Kleene star).
- Concatenazione: Permette di concatenare due simboli o stringhe.
- Unione (alternanza): Permette di scegliere tra più simboli o stringhe.
- Chiusura di Kleene: Permette di ripetere un simbolo o una stringa zero o più volte.
Esempio. L'espressione regolare `a(b|c)*` descrive tutte le stringhe che iniziano con 'a' seguita da una sequenza (anche vuota) di 'b' o 'c'. Questo include stringhe come "a", "ab", "ac", "abc", "abcc", ecc.
Le proprietà dei linguaggi
I linguaggi regolari possiedono alcune proprietà chiave che li rendono interessanti e utili:
- Chiusura: Sono chiusi sotto le operazioni di unione, concatenazione e chiusura di Kleene.
- Decidibilità: È possibile decidere in modo algoritmico se una stringa appartiene a un linguaggio regolare (problema di appartenenza).
- Equivalenza: È possibile determinare se due espressioni regolari descrivono lo stesso linguaggio.
Esempio. Se abbiamo due espressioni regolari `a*b` e `(aa)*b`, possiamo costruire automi per ciascuna e confrontarli per determinare se descrivono lo stesso insieme di stringhe.
Le grammatiche
Una grammatica è un insieme di regole formali che descrivono la struttura sintattica delle frasi in un linguaggio formale.
Queste regole definiscono come le stringhe di simboli possono essere generate e riconosciute all'interno del linguaggio.
Nota che la grammatica si distingue dal linguaggio.
- Grammatica
È l'insieme delle regole che specificano come costruire correttamente le frasi di un linguaggio. Serve a generare o riconoscere tutte le stringhe valide di un linguaggio. - Linguaggio
È l'insieme di tutte le stringhe che possono essere generate seguendo le regole della grammatica.
Esempio. Consideriamo una grammatica formale \( G \) definita come segue:
- Simboli non terminali (N): S (simbolo iniziale)
- Simboli terminali (T): a, b
- Regole di produzione (P):
1. \( S \rightarrow aSb \)
2. \( S \rightarrow \epsilon \) (dove \( \epsilon \) rappresenta la stringa vuota)
Le regole di produzione come \( S \rightarrow aSb \) e \( S \rightarrow \epsilon \) definiscono come sostituire i simboli non terminali con sequenze di simboli terminali e non terminali, permettendo la generazione delle stringhe del linguaggio.
- \( S \) è un simbolo non terminale che può essere sostituito seguendo le regole di produzione.
- Regola \( S \rightarrow aSb \): Indica che \( S \) può essere sostituito con "aSb", aggiungendo un 'a' all'inizio e un 'b' alla fine, mantenendo \( S \) al centro.
- Regola \( S \rightarrow \epsilon \):Indica che \( S \) può essere sostituito con la stringa vuota, terminando il processo di sostituzione.
Ad esempio per generare la stringa "aabb":
- Partiamo da \( S \).
- Applichiamo \( S \rightarrow aSb \) per ottenere "aSb".
- Applichiamo \( S \rightarrow aSb \) su \( S \) per ottenere "aaSbb".
- Applichiamo \( S \rightarrow \epsilon \) su \( S \) per ottenere "aabb".
In generale, questa grammatica permette al linguaggio di generare tutte le stringhe che hanno un numero uguale di 'a' e 'b' con tutte le 'a' prima di tutte le 'b'.
- \( \epsilon \) (stringa vuota)
- \( ab \)
- \( aabb \)
- \( aaabbb \)
- ...
In conclusione, i linguaggi regolari, grazie alla loro semplicità, sono fondamentali nell'informatica teorica e costituiscono la base per la progettazione di parser, la validazione delle stringhe e numerose applicazioni pratiche nell'ingegneria del software e nell'elaborazione del linguaggio naturale.
