Automa finito deterministico
Cosa sono gli automi finiti deterministici
Un automa finito deterministico (AFD) è una quintupla. $$ A = (X,E,δ,x_0,X_f) $$
E' composto dai seguenti elementi:
- X è l'insieme finito di stati
- E è l'insieme finito degli eventi ossia l'alfabeto dei simboli
- δ è la funzione di transizione tra gli stati
- x0 è lo stato iniziale
- Xm è l'insieme degli stati finali
E' anche detto deterministic finite automation (DFA)
Nota. E' detto a "stati finiti" perché il numero degli stati X è finito. E' deterministico perché dato una coppia specifica di stato di partenza e un evento la funzione di transizione determina sempre lo stesso stato di destinazione.
Come rappresentare un automa
Posso rappresentare un automa finito deterministico con la tabella di transizione e il diagramma di transizione ( grafo ).
Nota. Nella tabella di transizione le colonne sono gli eventi mentre le righe sono gli stati di partenza.
In un grafo ogni nodo identifica uno stato.
Gli archi sono le funzioni di transizione da uno stato all'altro.
$$ x_n = δ(x_{n-1},e_n) $$
Gli input della funzione di transizione sono uno stato (xn-1) e un simbolo dell'alfabeto (e). Dove il simbolo e è un evento.
L'output della funzione di transizione è lo stato (xn) successivo.
Gli archi uscenti da un nodo x indicano quali eventi (simboli) possono verificarsi a partire dallo stato x.
In un DFA ogni stato deve avere una transizione per ogni simbolo dell'alfabeto.
Nota. Un automa DFA ha una quantità di memoria molto limitata, ossia finita, perché una volta fissati gli stati non si possono aggiungerne altri.
Non è però detto che sia definita una funzione di transizione dal nodo per qualsiasi simbolo dell'alfabeto (e). Alcune combinazioni (xj,ek) potrebbero anche mancare.
Gli eventi definiti a partire da uno stato sono detti eventi attivi o eventi abilitati e sono inclusi nell'insieme A(x).
$$ A(x) = \{ e \in E | ∂(x,e)! \} $$
Dove la notazione ∂(x,e)! indica che la transizione è definita.
Sicuramente, da uno stesso nodo non possono uscire due o più archi ( funzioni di transizione ) etichettati con lo stesso simbolo.
Un automa ha sempre un solo stato iniziale. Può invece avere più stati finali.
Lo stato iniziale (x0) è indicato con una freccia, mentre lo stato finale (x3) è indicato con un nodo cerchiato.
Nota. Gli archi circolari che collegano lo stesso nodo sono detti cappi. Sono situazioni in cui lo stato dell'automa diventa definitivo. Non cambia più.
Un esempio pratico
Ho un alfabeto composto dai simboli 0 e 1.
$$ E=\{ 0, 1 \} $$
Il linguaggio è un insieme con le parole che iniziano per 01.
$$ L=\{ w \in \{ 0, 1 \} | w \text{ inizia con 01} \} $$
L'automa analizza una stringa in input e verifica se i primo carattere è 0 o 1.
Se il primo carattere è 0, l'automa verifica se il secondo carattere è 1.
L'automa può trovarsi in quattro stati
$$ x_0 = \{ \} \\ x_1 = \{ 1 ∨ 0,1 \} \\ x_2 = \{ 0 \} \\ x_3 = \{ 0, 1 \} $$
Nota. Nello stato x1 il primo carattere rilevato è 1. In questo caso l'automa non verifica anche il secondo carattere perché sarebbe inutile farlo. Quindi, passa direttamente ad analizzare la stringa successiva.
Lo stato iniziale e x0.
Il diagrammi degli stati dell'automa è il seguente:
La corrispondente tabella di transizione è
$$ \begin{array}{c|lcr} ∂ & 0 & 1 \\ \hline x_0 & x_2 & x_1 \\ x_1 & & \\ x_2 & x_1 & x_3 \\ x_3 & & \end{array} $$
La produzione
Una produzione è una sequenza di transizioni.
Una transizione è il passaggio da uno stato x a un altro in conseguenza di un evento (e)
$$ x_n = δ(x_{n-1},e_n) $$
Quindi una produzione può essere indicata con una parola formata dalla sequenza dei simboli degli eventi (anche ripetuti).
$$ e_1e_2e_3...e_k $$
Esempio. Nell'esempio precedente passaggio dallo stato X0 allo stato X3 equivale alla produzione 01.
In un grafo ogni produzione è un cammino orientato da un nodo (stato A) a un altro (stato B).
Dove lo stato A/B non necessariamente deve essere lo stato iniziale e finale dell'automa.
La chiusura transitiva e riflessiva
La funzione δ* è una chiusura transitiva e riflessiva tale che a partire da uno stato x raggiunge lo stato xk tramite una determinata produzione w $$ δ(x,w)! $$
Per indicare che la produzione esiste si scrive anche $$ x_k=δ*(x,w)! $$
Esempio
Nell'esempio precedente per passare dal nodo 0 al nodo 3 si scrive
$$ x_3 = δ(x_0, 01) $$
Quindi la produzione w=01 esiste
$$ δ(x_0, 01)! $$
Nota. La parola vuota ε è la parola che consente a qualsiasi nodo x di restare sul nodo stesso. $$ x=δ*(x,w)! $$
La parola generata
Una parola w è generata all'automa G=(X,E,δ,x0,Xm) se esiste una produzione δ*(x0,w)! che genera w a partire dallo stato iniziale.
La parola accettata
Una parola w è accettata (o marcata) dall'automa G=(X,E,δ,x0,Xm) se esiste una produzione δ*(x0,w)! che genera w a partire dallo stato iniziale e raggiunge lo stato finale.
In un grafo una parola accettata è un cammino orientato che collega il nodo iniziale e finale.
L'insieme di tutte le produzioni di un automa determina il linguaggio dell'automa.
Il linguaggio dell'automa
Il linguaggio di un automa a stati finiti (AFD) è l'insieme di tutte le sequenze di eventi w (produzioni) che realizzano una transizione dallo stato iniziale a un altro stato Xk qualsiasi.
Quindi, il linguaggio è un sottoinsieme di tutte le combinazioni possibili dell'alfabeto.
$$ L ⊆ E* $$
Esistono due tipologie di linguaggi in un automa
- Il linguaggio generato
Un linguaggio generato è l'insieme che contiene tutte le parole generate dall'automa AFD. $$ L(G) = \{ w \in E* | δ*(x_0,w)! \} ⊆ E* $$ Descrive le possibili evoluzioni del sistema. - Il linguaggio accettato (o marcato)
Un linguaggio accettato è l'insieme di tutte le parole accettate dall'automa AFD. $$ L_m(G) = \{ w \in E* | δ*(x_0,w) \in X_m \} ⊆ L(G) $$ Descrive il sottoinsieme delle evoluzioni del sistema che completano un'operazione specifica.Esempio. Tutte le evoluzioni che spengono la macchina, ossia che conducono l'automa in uno stato di spegnimento.
Il linguaggio accettato è un sottoinsieme del linguaggio generato.
$$ L_m(G) ⊆ L(G) $$
Nota. Il linguaggio generato è sempre chiuso per prefisso. Se una parola è generata allora anche il suo prefisso è generato. Viceversa, il linguaggio accettato non è necessariamente chiuso per prefisso.
La classe dei linguaggi di un AFD
L'insieme dei linguaggi accettati da un automa AFD è detta classe dei linguaggi AFD. $$ £_{AFD}=\{ L \:\: | \:\: ∃ \:\: G: \:\:L=L_m(G) \} $$
La classe dei linguaggi generati è inclusa nella classe dei linguaggi accettati.
Per questa ragione si prende in considerazione soltanto la classe dei linguaggi accettati.
Dimostrazione. Se un linguaggio è generato da un automa G, allora esiste anche un automa G' che lo accetta, basta rendere tutti gli stati di G come stati finali. Inoltre, ci sono linguaggi accettati da un AFD che non sono generati. E' sufficiente che non tutti gli stati siano finali. Un linguaggio accettato non è chiuso per prefisso, quindi non può appartenere a un linguaggio generato che per definizione è chiuso per prefisso. Quindi, l'inclusione è stretta.
E così via
