Torna alla pagina di Informatica Teorica
:: Informatica Teorica - Nondeterminismo ::
Appunti & Dimostrazioni del 17 Marzo
Le immagini di questa pagina sono prese dalle slide della prof Trucco
Concetti iniziali
Una computazione deterministica è quella in cui dato uno stato e un ingresso posso andare in un unico nuovo stato. Intuitivamente, in una computazione non deterministica (da ora n.d.
) dato uno stato e un ingresso posso andare a finire in un insieme di stati; in altre parole ogni stato può avere più di una transizione per ogni simbolo dell'alfabeto. A proposito di simboli, aggiungiamo al pacchetto quello di stringa vuota ε: si ha una transizione etichettata con ε quando si passa al nuovo stato senza leggere alcun ingresso.
Un automa finito n.d.
, o NFA, data una stringa di ingresso funziona così:
- tutte le volte che uno stato potrebbe avere più transizioni per diversi simboli dell'alfabeto, l'automa si duplica in più copie, ognuna delle quali segue il suo corso. Si vengono così a creare più rami di computazione indipendenti che sono eseguiti in parallelo;
- se il prossimo simbolo che dobbiamo passare a uno stato non si trova su nessuna delle sue frecce uscenti, si abbandona l'intero ramo di computazione che porta a lui;
- se almeno una delle copie raggiunge uno stato di accettazione, l'automa accetta la stringa di partenza;
- quando si incontra uno stato che ha il simbolo ε su una delle sue frecce in uscita, si duplica la macchina in più copie: quelle che seguono le ε in uscita, e quella che rimane nello stato corrente.
Con un esempio si fissano meglio le idee. Dato l'NFA:
Ecco l'albero di computazione corrispondente per la stringa di ingresso 010110
:
La rappresentazione ad albero è particolarmente utile perché basta una veloce occhiata per capire quali sono le sottostringhe che la stringa iniziale deve contenere perché sia accettata dall'automa. In questo caso sono 101
e 11
.
Definizione formale
La definizione formale di NFA è molto simile a quella dei DFA (Deterministic Finite Automaton, automi finiti deterministici), poiché entrambi hanno stati (di cui uno iniziale e almeno uno finale), un alfabeto di ingresso e funzioni di transizione. Sono proprio queste ultime a distinguerli, perché fa la sua comparsa il simbolo di stringa vuota ε.
Un automa a stati finiti non deterministico è una 5-tupla (Q, Σ, δ, q0, F) dove:
- Q è l'insieme finito degli stati dell'automa
- Σ è un insieme finito di simboli chiamato alfabeto
- δ: Q × Σε → P(Q) è la funzione di transizione. Σε significa che consideriamo l'unione tra gli insiemi Σ ed {ε}
- q0 ∈ Q è lo stato iniziale dell'automa
- F ⊆ Q è l'insieme degli stati accettanti
La definizione formale dell'NFA dell'esempio sopra sarà quindi:
1. Q = {q1, q2, q3, q4}
2. Σ = {0,1}
3. δ è dato da:
| 0
| 1
| ε
|
q1
| {q1}
| {q1,q2}
| 0
|
q2
| {q3}
| 0
| {q3}
|
q3
| 0
| {q4}
| 0
|
q4
| {q4}
| {q4}
| 0
|
4. q1 è lo stato di partenza
5. F = {q4}
Definizione formale di computazione
Sia dato un automa n.d.
N=(Q,Σ,δ,q0,F), ed una stringa di ingresso w tale che w = y1y2..ym , dove ogni yi fa parte dell'alfabeto Σε.
Diciamo che N accetta w se esiste una sequenza di stati r0r1..rm in Q che rispettino tre condizioni:
- r0 = q0 (la macchina parte dallo stato iniziale);
- ri+1 ∈ δ(ri,yi+1), per ogni i = 0, ... , m-1 (lo stato futuro è uno dei possibili prossimi stati quando N è in ri e legge yi+1);
- rm ∈ F (la macchina accetta l'ingresso se l'ultimo stato è tra quelli finali).
Teorema 1 - sull'equivalenza tra NFA e DFA
Automi deterministici e non deterministici riconoscono la stessa classe di linguaggi, il che è anti-intuitivo perché questi ultimi sembrano più potenti. Ma se riconoscono gli stessi linguaggi significa che sono equivalenti, sarà vero?
Ogni automa a stati finiti n.d.
ha un automa a stati finiti deterministico equivalente.
Dimostrazione
L'idea è quella di dimostrare il teorema per costruzione, ovvero provare che è possibile costruire un DFA equivalente ad un NFA dato. In pratica, dato un automa n.d.
N=(Q,Σ,δ,q0,F) che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(Q',Σ',δ',q0',F') che riconosca A.
Distinguiamo due casi: il caso (1) in cui non ci sono stati con frecce uscenti etichettate con ε, e il caso (2) in cui ci sono.
Caso (1)
- Q' = P(Q)
P(Q) è l'insieme di sottoinsiemi di Q, e l'equivalenza significa che il DFA deve avere uno stato per ogni possibile sottostato di N
- dato R lo stato di M in cui ci troviamo (R ∈ Q'), e considerando un simbolo a ∈ Σ, sia:
δ'(R,a) = {q ∈ Q | q ∈ δ(r,a) per r ∈ R}
- q0' = {q0}
Gli stati di partenza corrispondono
- F' = {R ∈ Q' | R contiene uno stato finale di N}
L'automa M accetta se uno dei possibili stati in cui si può trovare N è accettante.
Caso (2)
Considerando anche gli ε, dovremo trovare un modo per includerli nella notazione: per ogni stato R di M definiamo E(R) l'insieme di stati che possono essere raggiunti da R viaggiando attraverso le frecce ε, R incluso. Più formalmente, per R ∈ Q:
E(R) = {q | q può essere raggiunto da R viaggiando attraverso 0 o più frecce ε}
Ecco allora come cambia la quintupla (le corrispondenze uguali al Caso (1) non saranno ricommentate):
- Q' = P(Q)
- dato R lo stato di M in cui ci troviamo (R ∈ Q'), e considerando un simbolo a ∈ Σ, sia:
δ'(R,a) = {q ∈ Q | q ∈ E(δ(r,a)) per r ∈ R}
In questo modo la funzione di transizione di M terrà conto degli stati che possono essere raggiunti attraverso le frecce ε
- q0' = E({q0})
Lo stato iniziale di M tiene conto degli eventuali stati che potrebbero essere raggiunti dallo stato iniziale di N attraverso frecce ε
- F' = {R ∈ Q' | R contiene uno stato finale di N}
Seguendo le indicazioni descritte nei casi (1) e (2) è possibile costruire correttamente un DFA M che corrisponde a un NFA N: la dimostrazione del teorema è completa!
Esempio
Dato il seguente NFA:
Ecco il DFA corrispondente:
Corollario al Teorema 1
Un linguaggio è regolare se e solo se esiste un automa a stati finiti n.d.
che lo riconosce.
Dimostrazione
Il teorema è un "se e solo se", quindi vanno dimostrati entrambi i sensi delle implicazioni.
Se un automa n.d.
riconosce un linguaggio allora questo è regolare
Un linguaggio è regolare se esiste un automa a stati finiti deterministico che lo riconosce. Ma abbiamo appena visto nel Teorema 1 che ogni NFA può essere convertito in un DFA equivalente, quindi entrambi riconoscono la stessa classe di linguaggi, quindi anche quelli regolari.
Se un linguaggio è regolare allora esiste un automa n.d.
che lo riconosce
Dato che gli automi n.d.
sono una generalizzazione di quelli deterministici, un DFA è anche un NFA, quindi se il linguaggio è riconosciuto da uno lo è anche dall'altro.
Chiusura rispetto alle operazioni regolari
Le operazioni regolari sono unione, concatenazione e star. Si dice che una collezione di oggetti è chiusa rispetto ad una determinata operazione se applicandola ai membri della collezione si ottiene un oggetto che appartiene ancora alla collezione stessa.
Teorema 2 - sulla chiusura rispetto l'operazione di unione
La classe di linguaggi regolari è chiusa rispetto all'operazione di unione.
Dimostrazione
Abbiamo due linguaggi A1 e A2 e vogliamo dimostrare che la loro unione è regolare. L'idea è quella di prendere due automi n.d.
N1 ed N2 che li riconoscano (rispettivamente) e combinarli in un nuovo NFA N, che dovrà accettare la stringa in ingresso se uno dei due la accetta. Dato che ogni Ni ha propri stati iniziali e finali, come li dobbiamo combinare?
Basta aggiungere un nuovo stato iniziale che con frecce ε si colleghi ai vecchi stati iniziali, così da avere garanzia che la stringa in ingresso arrivi a entrambi gli Ni, e se uno di loro accetta tutto N accetta! Vediamo in figura che si capisce meglio:
Più formalmente, siano dati due automi n.d.
:
- N1=(Q1,Σ,δ1,q1,F1) che riconosce il linguaggio A1;
- N2=(Q2,Σ,δ2,q2,F2) che riconosce il linguaggio A2.
La costruzione di N=(Q,Σ,δ,q0,F) che riconosce l'unione dei linguaggi A1 e A2 va fatta così:
- Q = {q0} U Q1 U Q2
Gli stati di N sono tutti quelli di N1 più quelli di N2 più il nuovo stato iniziale q0
- Σ non cambia
- q0 è il nuovo stato iniziale
- F = F1 U F2
N accetta se o N1 o N2 accettano
- definiamo la δ in modo che per q∈Q e a∈Σε si abbia:
Teorema 3 - sulla chiusura rispetto l'operazione di concatenazione
La classe di linguaggi regolari è chiusa rispetto all'operazione di concatenazione.
Dimostrazione
Abbiamo due linguaggi A1 e A2 e vogliamo dimostrare che la loro concatenazione è regolare. L'idea è quella di prendere due automi n.d.
N1 ed N2 che li riconoscano (rispettivamente) e combinarli in un nuovo NFA N. Dato che ogni Ni ha propri stati iniziali e finali, come li dobbiamo combinare?
- lo stato iniziale di N deve corrispondere a quello di N1, quindi i due riconosceranno le stesse stringhe di ingresso;
- gli stati finali di N1 vanno collegati a quello iniziale di N2 con frecce ε;
- lo stato finale di N deve corrispondere a quello di N2.
Anche in questo caso si capisce meglio in figura:
Più formalmente, siano dati due automi n.d.
:
- N1=(Q1,Σ,δ1,q1,F1) che riconosce il linguaggio A1;
- N2=(Q2,Σ,δ2,q2,F2) che riconosce il linguaggio A2.
La costruzione di N=(Q,Σ,δ,q1,F2) che riconosce la concatenazione dei linguaggi A1 e A2 va fatta così:
- Q = Q1 U Q2
Gli stati di N sono tutti quelli di N1 più quelli di N2
- Σ non cambia
- q1 è lo stato iniziale
- F2 è l'insieme degli stati finali
- definiamo la δ in modo che per q∈Q e a∈Σε si abbia:
Teorema 4 - sulla chiusura rispetto l'operazione di star
La classe di linguaggi regolari è chiusa rispetto all'operazione di star.
Dimostrazione
L'operazione star è quella che ci permette di concatenare per un certo numero di volte la stessa stringa.
Abbiamo un linguaggio A e vogliamo dimostrare che il suo star A* è regolare. L'idea è quella di prendere l'automa n.d.
N1 che lo riconosce e realizzare un nuovo NFA N che implementi lo star. Lo costruiamo mettendo delle frecce ε addizionali che vadano dagli stati finali di N1 a quello iniziale di N1, così che si possa ricominciare il giro. Dato che stiamo usando un automa n.d.
non possiamo trascurare il fatto che la stringa passata in ingresso potrebbe essere vuota: la ripetizione di una stringa vuota è una stringa vuota, quindi lo stato iniziale di N dovrà essere anche tra quelli finali. Il nuovo stato iniziale è collegato a quello vecchio di N1 da una solita freccia ε.
Vediamo in figura:
Più formalmente, sia dato l'automa n.d.
:
- N1=(Q1,Σ,δ1,q1,F1) che riconosce il linguaggio A1.
La costruzione di N=(Q1,Σ,δ1,q0,F1) che riconosce lo star del linguaggio A1 va fatta così:
- Q = {q0} U Q1
- Σ non cambia
- q0 è il nuovo stato iniziale
- F = {q0} U F1
- definiamo la δ in modo che per q∈Q e a∈Σε si abbia:
Torna alla pagina di Informatica Teorica