Automi a stati finiti deterministici
Un’automa a stati finiti deterministico (DFSA, dall’inglese Deterministic Finite State Automaton) è definito dalla tupla (Q, F, q0, I, δ), in cui:
- Q è l’insieme degli stati. Q è un insieme finito.
- F è l’inisieme degli stati finali o stati di accettazione. F è un sottoinsieme di Q.
- q0 è lo stato iniziale.
- I è l’alfabeto dei simboli di ingresso.
- δ è la funzione di transizione.
La funzione di transizione
Per un DFSA, la funzione di transizione è così definita:
δ: Q x I → Q
Ovvero: considerato lo stato attuale e il simbolo di ingresso attuale, la funzione di transizione indica qual è il nuovo stato da raggiungere.
La transizione
Ecco un esempio di transizione in un DFSA:
La transizione qui sopra indica che, se l’automa è nello stato A e in ingresso è letto il simbolo a, allora bisogna passare allo stato B.
Il diagramma degli stati
Un’automa può essere efficacemente rappresentato attraverso un diagramma degli stati. Ecco un esempio di diagramma degli stati per un DFSA:
Lo stato iniziale è indicato attraverso una freccia che parte dal nulla e raggiunge tale stato.
Gli stati finali sono contraddistinti da una doppia circolettatura.
La tabella di transizione
Una funzione di transizione può essere efficacemente rappresentata attraverso una tabella di transizione.
Ecco un esempio di tabella di transizione, riferita all’automa dell’esempio precedente:
| Q\I | a | b |
|---|---|---|
| even | odd | odd |
| odd | even | even |