Cos’è un automa a stati finiti

Un automa a stati finiti può essere formalmente descritto come una quintupla (Q,Σ,δ,q0,F)(Q,Σ,δ,q0​,F), dove:

• $Q$ è un insieme finito di stati dell’automa.
• $\Sigma$ è l’alfabeto degli input, cioè l’insieme finito di simboli che l’automa può leggere.
• $\delta$ è la funzione di transizione, che specifica come l’automa cambia di stato in risposta agli input. Formalmente, $\delta :Q\times \Sigma \to 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.
• $F$ è 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}
• $\delta$ è 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