Nel precedente articolo abbiamo parlato di come costruire gli automi.

In questo articolo parleremo della relazione tra automi a stati finiti ed i linguaggi regolari.

Linguaggi regolari

Un linguaggio regolare è un linguaggio formale generato da una grammatica generativa regolare (o di tipo 3, secondo la gerarchia di Chomsky) o accettato da un automa a stati finiti (automa a stati finiti deterministico o automa a stati finiti non deterministico).

Possiamo quindi dire che la classe dei linguaggi regolari equivale alla classe dei linguaggi di tipo 3 che equivale alla classe dei linguaggi descrivibili da un automa a stati finiti. (Teorema di Kleene).

Proviamo ora a costruire un automa che descrive il seguente linguaggio:

L = {B A ^ n B | n > 0} 

Esaminando il linguaggio possiamo dire che le parole che fanno parte del linguaggio stesso sono:

• Tutte le parole che iniziano e finiscono con B, che hanno inoltre almeno una a tra le due B.

L’ automa dovrà dunque leggere all’ inizio una B, dopo dovrà leggere un numero di A >= 1, per poi chiudere alla fine con un’ altra B.

Tutte le altre combinazioni di parole non saranno accettate dall’ automa.

Costruire l’ automa

L’ automa descrive perfettamente il linguaggio di cui sopra, infatti legge dapprima una B, recandosi nello stato q1. Da questo stato legge una A e si reca in uno stato q2, da quest’ ultimo si aspetta di leggere una A e rimanere in q2 oppure si aspetta di leggere una B ed andare in q3, in cui la stringa è accettata.

Proviamo a costruire la tabella di transizione:

Sei arrivato alla fine di quest’ultimo articolo introduttivo, se vuoi iniziare ad esercitarti, vai al primo esercizio.

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.

Alla prossima!