Automi a stati finiti

Possiamo formalizzare l'accettazione di un linguaggio su , da parte di un FSA come: Dove , è una sequenza di mosse, estensione di induttivamente definita come:

Di seguito un FSA riconoscitore per un linguaggio

Di seguito un FSA riconoscitore del linguaggio degli identificatori del linguaggio c. Si ha che è definito su :

Un FSA traduttore da a associa un simbolo letto e uno scritto a ogni transizione.

Formalmente un FSA traduttore è una -upla , dove:

• sono come nell'FSA riconoscitore
• è l'alfabeto di uscita
• è la funzione di traduzione.

Formalizziamo, analogamente a , come successione di traduzioni di elementi, e quindi come traduzione di stringhe: Di conseguenza l'intero calcolo della traduzione è formalizzato come:

Di seguito un FSA traduttore che traduce da a , entrambi definiti su , con un numero di pari, aventi funzione di traduzione che dimezza gli e raddoppia gli .

Il pumping lemma è la formalizzazione di un comportamento ciclico in un FSA, cioè l'esistenza di un ciclo percorribile volte.
Il pumping lemma afferma che se , dove è un linguaggio riconosciuto da un FSA, con (dove è l'insieme degli stati), allora esistono e tali che con e , cioè esiste una sottostringa di che viene riconosciuta dall'automa effettuando un'iterazione su un ciclo di stati.

Dal pumping lemma consegue che , che segue dal poter effettuare zero o più iterazioni del ciclo.

Un FSA non può riconoscere un linguaggio .
Per dimostrarlo, sia con . Applicando il pumping lemma si ha che , con una tra le seguenti forme:

• , pompando ottengo che è assurdo.
• , pompando ottengo che è assurdo.
• , pompando ottengo che è assurdo.

La famiglia di linguaggi riconoscibili con un FSA è detta famiglia dei linguaggi regolari o REG. Si ha che è chiusa rispetto a .

Una famiglia di linguaggi è un insieme i cui elementi sono linguaggi . è chiusa rispetto ad un operazione binaria se vale .

Dati due FSA riconoscitori:

È possibile ottenere il riconoscitore del linguaggio intersezione facendoli funzionare insieme, con la condizione che di effettuare una transizione solo se c'è in entrambi:

Formalmente, dati due FSA e , si ha che l'automa intersezione è dato da:

• Insieme degli stati
• Alfabeto
• Funzione di transizione
• Insieme degli stati finali

Inoltre si ha che:

Dati due FSA:

Si ha nel FSA intersezione che lo stato in rosso non è raggiungibile dallo stato iniziale e quindi può essere eliminato, e che con la costruzione a punto fisso a partire da non viene neppure aggiunto:

Formalmente, dati due automi e , l'automa unione è dato da:

• Insieme degli stati
• Alfabeto
• Funzione di transizione
• Insieme degli stati finali

In alternativa è possibile applicare la legge di De Morgan:

Si ha che in ogni FSA esiste uno stato non accettante implicito, detto stato di errore. Aggiunto quello è possibile scambiare gli stati finali e gli stati non finali .