Swappa : Uni / Informatica Teorica

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, Σ, δ, q₀, 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 {ε}
q₀ ∈ 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 = {q₁, q₂, q₃, q₄}

2. Σ = {0,1}

3. δ è dato da:

	0	1	ε
q₁	{q₁}	{q₁,q₂}	0
q₂	{q₃}	0	{q₃}
q₃	0	{q₄}	0
q₄	{q₄}	{q₄}	0

4. q₁ è lo stato di partenza

5. F = {q₄}

Definizione formale di computazione

Sia dato un automa n.d. N=(Q,Σ,δ,q₀,F), ed una stringa di ingresso w tale che w = y₁y₂..y_m , dove ogni y_i fa parte dell'alfabeto Σ_ε.
Diciamo che N accetta w se esiste una sequenza di stati r₀r₁..r_m in Q che rispettino tre condizioni:

r₀ = q₀ (la macchina parte dallo stato iniziale);
r_i+1 ∈ δ(r_i,y_i+1), per ogni i = 0, ... , m-1 (lo stato futuro è uno dei possibili prossimi stati quando N è in r_i e legge y_i+1);
r_m ∈ 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,Σ,δ,q₀,F) che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(Q',Σ',δ',q₀',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}
q₀' = {q₀}
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 ε
q₀' = E({q₀})
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 A₁ e A₂ e vogliamo dimostrare che la loro unione è regolare. L'idea è quella di prendere due automi n.d. N₁ ed N₂ 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 N_i 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 N_i, e se uno di loro accetta tutto N accetta! Vediamo in figura che si capisce meglio:

Più formalmente, siano dati due automi n.d.:

N₁=(Q₁,Σ,δ₁,q₁,F₁) che riconosce il linguaggio A₁;
N₂=(Q₂,Σ,δ₂,q₂,F₂) che riconosce il linguaggio A₂.

La costruzione di N=(Q,Σ,δ,q₀,F) che riconosce l'unione dei linguaggi A₁ e A₂ va fatta così:

Q = {q₀} U Q₁ U Q₂
Gli stati di N sono tutti quelli di N₁ più quelli di N₂ più il nuovo stato iniziale q₀
Σ non cambia
q₀ è il nuovo stato iniziale
F = F₁ U F₂
N accetta se o N₁ o N₂ 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 A₁ e A₂ e vogliamo dimostrare che la loro concatenazione è regolare. L'idea è quella di prendere due automi n.d. N₁ ed N₂ che li riconoscano (rispettivamente) e combinarli in un nuovo NFA N. Dato che ogni N_i ha propri stati iniziali e finali, come li dobbiamo combinare?

lo stato iniziale di N deve corrispondere a quello di N₁, quindi i due riconosceranno le stesse stringhe di ingresso;
gli stati finali di N₁ vanno collegati a quello iniziale di N₂ con frecce ε;
lo stato finale di N deve corrispondere a quello di N₂.

Anche in questo caso si capisce meglio in figura:

Più formalmente, siano dati due automi n.d.:

N₁=(Q₁,Σ,δ₁,q₁,F₁) che riconosce il linguaggio A₁;
N₂=(Q₂,Σ,δ₂,q₂,F₂) che riconosce il linguaggio A₂.

La costruzione di N=(Q,Σ,δ,q₁,F₂) che riconosce la concatenazione dei linguaggi A₁ e A₂ va fatta così:

Q = Q₁ U Q₂
Gli stati di N sono tutti quelli di N₁ più quelli di N₂
Σ non cambia
q₁ è lo stato iniziale
F₂ è 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. N₁ 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 N₁ a quello iniziale di N₁, 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 N₁ da una solita freccia ε.
Vediamo in figura:

Più formalmente, sia dato l'automa n.d.:

N₁=(Q₁,Σ,δ₁,q₁,F₁) che riconosce il linguaggio A₁.

La costruzione di N=(Q₁,Σ,δ₁,q₀,F₁) che riconosce lo star del linguaggio A₁ va fatta così:

Q = {q₀} U Q₁
Σ non cambia
q₀ è il nuovo stato iniziale
F = {q₀} U F₁
definiamo la δ in modo che per q∈Q e a∈Σ_ε si abbia:

Torna alla pagina di Informatica Teorica