Fondamenti di informatica - Laurea triennale Informatica/Automi a stati finiti
L' automa a stati finiti (finite-state automata) è un tipo particolare di macchina a stati finiti usato per riconoscere stringhe e linguaggi.
Un automa a stati finiti è una macchina con un numero finito di stati. A differenza di una macchina a stati finiti generica, il suo output è solo 0 o 1: gli stati associati all’output 1 sono detti stati accettanti. Se, dopo aver letto una stringa, l’automa termina in uno stato accettante, allora la stringa viene accettata; altrimenti viene rifiutata.
Il capitolo spiega che un automa può essere rappresentato con un diagramma di transizione. In questi diagrammi:
- gli stati sono rappresentati da cerchi;
- lo stato iniziale è indicato da una freccia entrante;
- gli stati accettanti sono rappresentati con doppi cerchi;
- le frecce indicano come l’automa cambia stato quando legge un simbolo di input.
Riprendendo l'esempio del precedente capitolo:
|
Diagramma di stato 
|
- S1 è l'unico stato accettante ed è anche lo stato iniziale.
- Se è dato come input 1 lo stato S1 si conserva ed è (accettato)
- se allo stato S1 si da input 0 lo stato passa ad S2 (non accettato)
- Se allo stato S2 si da input 1 lo stato permane S2 (non accettato)
- Se allo stato S2 si da input 0 lo stato passa ad S1 (accettato)
- La macchina accetta quindi solo la sequenza 10
Un automa a stati finiti può essere descritto formalmente tramite:
- un insieme finito di simboli di input;
- un insieme finito di stati;
- una funzione che stabilisce il prossimo stato;
- un insieme di stati accettanti;
- uno stato iniziale.
Quando si inserisce una stringa nell’automa, esso parte dallo stato iniziale e legge i simboli uno alla volta. Ogni simbolo determina una transizione verso un nuovo stato. Il percorso seguito dall’automa è detto percorso rappresentante la stringa. La stringa viene accettata se il percorso termina in uno stato accettante.
Un automa a stati finiti può essere visto anche come un algoritmo: dato un input, l’automa decide in modo meccanico se accettarlo o rifiutarlo. Per esempio, un algoritmo può controllare se una stringa contiene un numero dispari di lettere a, aggiornando lo stato ogni volta che incontra quel simbolo.
Gli automi sono equivalenti se accettano esattamente lo stesso insieme di stringhe. In altre parole, anche se hanno diagrammi o numeri di stati diversi, sono equivalenti se riconoscono lo stesso linguaggio.