Fondamenti di informatica - Laurea triennale Informatica/Relazioni fra linguaggi e automi

Approfondiamo ora il legame tra linguaggi regolari, grammatiche regolari, automi finiti deterministici e automi finiti non deterministici.

Tutti questi modelli, pur essendo descritti in modi diversi, hanno la stessa potenza nel riconoscere i linguaggi regolari.

Da automi non deterministici ad automi deterministici

Ricordando che:

• ogni automa finito può essere associato a una grammatica regolare;
• ogni grammatica regolare può essere associata a un automa finito non deterministico.

Possiamo quindi affermare che ogni automa finito non deterministico può essere trasformato in un automa finito deterministico equivalente.

Il metodo usato è la costruzione per sottoinsiemi. In pratica si definisce un nuovo stato che definisce l'unione dei due stati alternativi e da li si ricalcola tutto l'automa come automa a stati finiti

Se un automa non deterministico ha un insieme di stati S, allora l’automa deterministico equivalente avrà come stati tutti i sottoinsiemi di S. Ogni nuovo stato rappresenta quindi un insieme di stati in cui l’automa non deterministico potrebbe trovarsi dopo aver letto una certa stringa.

Lo stato iniziale del nuovo automa è l’insieme contenente solo lo stato iniziale dell’automa originale. Gli stati accettanti sono tutti quei sottoinsiemi che contengono almeno uno stato accettante dell’automa non deterministico.

In questo modo si ottiene un automa deterministico che accetta esattamente le stesse stringhe dell’automa non deterministico.

Teorema fondamentale

Il risultato centrale è il seguente:

Un linguaggio è regolare se e solo se esiste un automa finito che accetta esattamente le sue stringhe.

Questo significa che le grammatiche regolari e gli automi finiti descrivono la stessa classe di linguaggi: i linguaggi regolari.

Quindi, per dimostrare che un linguaggio è regolare, basta costruire un automa finito che lo riconosce. Al contrario, se un linguaggio è generato da una grammatica regolare, allora esiste anche un automa finito che lo accetta.

Esempio di linguaggio non regolare

Il linguaggio

L={aⁿbⁿ∣n≥0}

non è regolare.

La dimostrazione è questa: se il linguaggio fosse regolare, dovrebbe esistere un automa finito che lo accetta. Ma un automa finito ha un numero limitato di stati. Se legge una stringa molto lunga del tipo

aⁿbⁿ

con molti simboli a, prima o poi deve ripassare per uno stesso stato mentre legge le a. Questo crea un ciclo. Ripetendo quel ciclo, l’automa accetterebbe una stringa con più a che b, per esempio:

a^n+kbⁿ

ma questa stringa non appartiene al linguaggio L. Si ottiene quindi una contraddizione. Perciò il linguaggio non è regolare.

Questo esempio è importante perché mostra un limite degli automi finiti: non possono “ricordare” un numero arbitrario di simboli per confrontarlo con un altro numero arbitrario di simboli successivi.

Linguaggi inversi

E' possibile costruire un automa che accetta le stringhe inverse di quelle accettate da un dato automa.

Se un automa accetta un linguaggio L e si vuole costruire un automa che accetti:

L^R={w^R∣w∈L}

cioè il linguaggio formato dalle stringhe lette al contrario.

Il metodo consiste nel:

1. invertire la direzione di tutte le frecce dell’automa;
2. scambiare il ruolo dello stato iniziale e degli stati finali;
3. se ci sono più stati finali, introdurre un nuovo stato finale unico per semplificare la costruzione;
4. ottenere eventualmente un automa non deterministico;
5. se necessario, trasformarlo poi in un automa deterministico equivalente.

Questo dimostra che anche il linguaggio inverso di un linguaggio regolare è regolare.