[Introduzione alla teoria della computazione] Esercizio 1.16

[FeddyLix17]

Usare la costruzione data nel Teorema 1.39 per trasformare i due automi finiti non deterministici seguenti in automi finiti deterministici equivalenti.

Teorema 1.39

Per ogni automa finito non deterministico esiste un automa finito deterministico equivalente.

---

IDEA.   Se un linguaggio è riconosciuto da un NFA, allora dobbiamo mostrare l'esistenza di un DFA che lo riconosce.

L'idea è trasformare l'NFA in un DFA equivalente che simula l'NFA.

Ricorda la strategia "lettore come automa" per progettare automi finiti.

Come simuleresti l'NFA se stessi immaginando di essere un DFA? Cosa devi memorizzare dell'elaborazione della stringa di input?

Negli esempi degli NFA, mantenevi traccia dei vari rami della computazione ponendo un dito su ogni stato che potrebbe essere attivo in specificati punti nell'input.

Aggiornavi la simulazione muovendo, aggiungendo e rimuovendo dita in base al modo in cui l'NFA opera.

Tutto quello di cui dovevi tenere traccia era l'insieme degli stati che avevano dita su essi.

Se k è il numero degli stati dell'NFA, esso ha 2^k sottoinsiemi di stati.

Ogni sottoinsieme corrisponde a una delle possibilità che il DFA deve ricordare, quindi il DFA che simula l'NFA avrà 2^k stati.

Ora noi dobbiamo capire quali saranno lo stato iniziale e gli stati accettanti del DFA, e quale sarà la sua funzione di transizione.

Possiamo discutere di questo più facilmente dopo aver introdotto alcune notazioni formali.

---

DIMOSTRAZIONE   Sia N = (Q, Σ, δ, q₀, F) l'NFA che riconosce un linguaggio A.

Costruiamo un DFA M = ( Q^', Σ, δ^', q₀^', F^' ) che riconosce A.

Prima di fare la costruzione completa, consideriamo inizialmente il caso più semplice in cui N non ha ε-archi.

In seguito considereremo gli ε-archi.

1. Q^' = ℙ(Q). Ogni stato di M è un insieme di stati di N. Ricorda che ℙ(Q) è l'insieme dei sottoinsiemi di Q.

2. R ∈ Q^' e a ∈ Σ, sia

$$ \Large \delta'(R,\ a) = \{q \in Q | q \in \delta(r,\ a)\ \text{per qualche}\ r \in R\}. $$

     Se R è uno stato di M, esso è anche un insieme di stati di N.

     Quando M legge un simbolo a nello stato R, mostra dove a porta ogni stato in R.

     Poichè da ogni stato si può andare in un insieme di stati, prendiamo l'unione di tutti questi insiemi.

     Un altro modo per scrivere questa espressione è

$$ \Large \delta'(R,\ a) = \bigcup_{r \in R} \delta(r,\ a). $$

     Ovvero l'unione degli insiemi δ(r, a) per ogni possibile r in R.

3. q₀' = { q₀ }. M inizia nello stato corrispondente alla collezione che contiene solo lo stato iniziale di N.

$$ \Large F' = \{R \in Q' | R\ \text{contiene uno stato accettante di N}\}. $$

     La macchina M accetta se uno dei possibili stati in cui N potrebbe essere a quel punto è uno stato accettante.

Ora dobbiamo considerare gli ε-archi. Per farlo, introduciamo qualche ulteriore notazione.

Per ogni stato R di M, definiamo E(R) come la collezione di stati che possono essere raggiunti dagli elementi di R proseguendo solo con ε-archi, includendo gli stessi elementi di R.

Formalmente, per R ⊆ Q sia

$$ \Large E(R) = \{q | q\ \text{può essere raggiunto da R attraverso 0 o più}\ \epsilon \text{-archi}\}. $$

Poi modifichiamo la funzione di transizione di M ponendo dita supplementari su tutti gli stati che possono essere raggiunti proseguendo attraverso ε-archi dopo ogni passo.

Sostituendo δ(r, a) con E(δ(r, a)) realizziamo questo effetto. Quindi

$$ \Large \delta'(R,\ a) = \{ q \in Q | q \in E(\delta(r,\ a))\ \text{per qualche}\ r \in R\}. $$

Inoltre, dobbiamo modificare lo stato iniziale di M per muovere inizialmente le dita su tutti i possibili stati che possono essere raggiunti dallo stato iniziale di N attraverso di ε-archi.

Cambiare q₀' in E( { q₀ } ) realizza questo risultato. Ora abbiamo completato la costruzione del DFA M che simula l'NFA N.

Ovviamente la costruzione di M funziona correttamente.

A ogni passo nella computazione di M su un input, chiaramente entra in uno stato che corrisponde al sottoinsieme di stati in cui N potrebbe essere a quel punto. Quindi la nostra prova è completa.

Il Teorema 1.39 afferma che ogni NFA può essere trasformato in un DFA equivalente.

Quindi gli automi finiti non deterministici forniscono un modo alternativo di caratterizzare i linguaggi regolari.

Esprimiamo questo fatto come corollario del Teorema 1.39.

---

COROLLARIO 1.40

Un linguaggio è regolare se e solo se qualche automa finito non deterministico lo riconosce.

Una direzione della condizione "se e solo se" afferma che un linguaggio è regolare se qualche NFA lo riconosce.

Il Teorema 1.39 mostra che ogni NFA può essere trasformato in un DFA equivalente. Conseguentemente, se un NFA riconosce un linguaggio, lo fa anche qualche DFA, e quindi il linguaggio è regolare.

L'altra direzione della condizione "se e solo se" afferma che un linguaggio è regolare solo se qualche NFA lo riconosce.

Cioè, se un linguaggio è regolare, qualche NFA deve riconoscerlo.

Ovviamente, questa condizione è vera perché un linguaggio regolare ha un DFA che lo riconosce e un DFA è anche un NFA.