Automi finiti

DFA

Un'automa a stati finiti deterministico (o DFA) $D$ è definito come una quintupla $(Q, Σ, δ, q_{0}, F)$ , dove:

$Q$ è l'insieme finito di stati
$Σ$ è l'alfabeto finito degli input
$δ : Q \times Σ \to Q$ è la funzione di transizione, definita per ogni input
$q_{0} \in Q$ è lo stato iniziale
$F \subseteq Q$ è l'insieme degli stati accentanti finali

Una stringa $w = w_{1} w_{2} \dots w_{n} : w_{i} \in Σ, \forall i = 1, ..., n$ è accettata da $M$ sse $\exists r_{0}, r_{1}, ..., r_{n} \in Q$ tale che:

$r_{0} = q_{0}$ : la sequenza di stati comincia dallo stato iniziale
$r_{n} \in F$ : alla fine dell'input si trova su uno stato accettante
$δ (r_{i}, w_{i + 1}) = r_{i + 1}, \forall i = 0, ..., n - 1$ : l' $(i + 1)$ -esimo input porta allo prossimo stato della sequenza

Per esempio, l'automa

sarà rappresentato dalla quintupla $D = (Q, Σ, δ, q_{0}, F)$ , dove: $Q Σ q_{0} F = {q_{1}, q_{2}} = {0, 1} = q_{1} = {q_{2}} \land ⎩ ⎨ ⎧ δ (q_{1}, 0) = q_{1} δ (q_{1}, 1) = q_{2} δ (q_{2}, 0) = q_{1} δ (q_{2}, 1) = q_{2}$

NFA

Un'automa a stati finiti non-deterministico (o NFA) è definito $N = (Q, Σ, δ, q_{0}, F)$ come un DFA, ma: $δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ dove $ϵ$ è la stringa vuota, infatti $∣ ϵ ∣ = 0$ , $P (Q)$ è l'insieme delle parti, e $\emptyset \in P (Q)$ è l'assenza di transizione.

Una stringa $w = y_{1} y_{2} \dots y_{m} : y_{i} \in Σ \cup {ϵ}, \forall i = 1, ..., m$ è accettata sse $\exists r_{0}, r_{1}, ..., r_{m} \in Q$ tale che:

$r_{0} = q_{0}$
$r_{m} \in F$
$r_{i + 1} \in δ (r_{i}, y_{i + 1}), \forall i = 1, ..., m - 1$

con $ϵ$ che fa parte di $w$ perchè $0010$ si può anche riscrivere come $00 ϵ 10$ o $ϵ 0010$ .

Per esempio,

accetta $101$ , $11$ e $0111$ . Nell'ultimo caso, i percorsi tentati sono illustrati dall'albero di computazione:

perchè $0111$ è riscrivibile come $011 ϵ 1$ .

Un altro esempio è l'automa che riconosce stringhe la cui lunghezza è divisibile per $2$ o $3$ :

Computer Science

Automi finiti

DFA

NFA