Un automa a stati finiti può essere formalmente descritto come una quintupla (Q,Σ,δ,q0,F)(Q,Σ,δ,q0,F), dove:
- QQ è un insieme finito di stati dell’automa.
- ΣΣ è l’alfabeto degli input, cioè l’insieme finito di simboli che l’automa può leggere.
- δδ è la funzione di transizione, che specifica come l’automa cambia di stato in risposta agli input. Formalmente, δ:Q×Σ→Qδ:Q×Σ→Q indica che dato uno stato e un input, l’automa si muoverà in un nuovo stato.
- q0q0 è lo stato iniziale, cioè lo stato in cui l’automa si trova all’inizio dell’esecuzione.
- FF è l’insieme degli stati finali, cioè gli stati in cui l’automa accetta l’input.
Ad esempio, considera un automa a stati finiti che riconosce stringhe che iniziano con ‘0’ e finiscono con ‘1’. La sua descrizione formale potrebbe essere:
- Q={q0,q1,q2}
- Σ={0,1}
- δδ è definita come:
- δ(q0,0)=q1
- δ(q1,0)=q1
- δ(q1,1)=q2
- δ(q2,0)=q2
- δ(q2,1)=q2
- q0=q0
- F={q2}
In questo esempio, l’automa inizia nello stato q0q0, e se legge ‘0’ passa allo stato q1q1, poi se legge ‘1’ passa a q2q2, dove rimane fino alla fine della stringa. Se l’automa si trova in q2q2 alla fine dell’input, accetta la stringa.
Dalla macchina di Turing agli automi a stati finiti
La relazione tra un automa a stati finiti e una macchina di Turing risiede nel fatto che entrambi sono modelli computazionali. Una macchina di Turing è un modello teorico di un computer, inventato da Alan Turing negli anni ’30, che opera seguendo una serie di istruzioni su un nastro infinito suddiviso in celle. Può leggere, scrivere e spostarsi su questo nastro, e le sue azioni sono guidate da una tabella di transizione che determina il suo comportamento in base allo stato corrente e al simbolo letto.
Si può pensare a un automa a stati finiti come a una versione semplificata di una macchina di Turing. Mentre le macchine di Turing sono più potenti e in grado di eseguire una vasta gamma di calcoli, gli automi a stati finiti sono più limitati nella loro capacità computazionale, ma sono ancora utili per modellare e comprendere alcuni tipi di problemi computazionali. In effetti, un automa a stati finiti può essere considerato un caso speciale di una macchina di Turing, dove il nastro è implicitamente finito e il modello computazionale è meno espressivo ma più semplice da analizzare.
https://www.youtube.com/watch?v=IFGLV8Bd-Dg