|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-Nondeterminismo History
Hide minor edits - Show changes to output
Changed lines 17-18 from:
* se ci troviamo su uno stato della copia della macchina, e il prossimo simbolo che gli si vuole passare non si trova su nessuna delle sue frecce uscenti, si abbandona tutto il ramo della computazione che porta fino a lui;
* se almeno una delle copie raggiunge al termine della computazione lo stato finale, l'automa accetta la stringa di partenza; to:
* 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; Changed lines 29-30 from:
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@] se si è nello stato ''q'_2_''', e [@11@] se siamo nello stato ''q'_3_'''. to:
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@]. Changed lines 82-83 from:
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? E a cosa servono i teoremi? to:
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? Changed lines 90-92 from:
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'_0_',F) che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(Q',Σ',δ',q'_0_'' ,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. Per ogni caso dovremo specificare come vanno messi in corrispondenza i vari elementi della quintupla. to:
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'_0_',F) che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(Q',Σ',δ',q'_0_'',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. Changed line 103 from:
to:
Changed line 109 from:
''δ'(R,''a'') = {q ∈ Q | q ∈ to:
''δ'(R,''a'') = {q ∈ Q | q ∈ E(δ(r,''a'')) per r ∈ R}''\\ Changed line 111 from:
to:
* q'_0_'' = E({q'_0_'})\\ Changed line 135 from:
''Se un automa [n.d.@] riconosce un linguaggio allora questo è regolare''\\ to:
''Se un automa [@n.d.@] riconosce un linguaggio allora questo è regolare''\\ Changed lines 167-168 from:
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia: to:
# definiamo la δ in modo che per q∈Q e ''a''∈Σ'_ε_' si abbia: Changed lines 196-197 from:
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia: to:
# definiamo la δ in modo che per q∈Q e ''a''∈Σ'_ε_' si abbia: Changed lines 208-209 from:
L'operazione star è quella che ci permette di concatenare per un certo numero di volte la stessa stringa (ringraziatemi).\\
Abbiamo un linguaggio A e vogliamo dimostrare che il suo star A* è regolare. L'idea è quella di prendere l'automa [@n.d.@] N'_1_' 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'_1_' a quello iniziale di N'_1_', 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 anche essere vuota: la ripetizione di una stringa vuota sarebbe una stringa vuota, quindi lo stato iniziale di N dovrebbe essere anche uno di quelli finali, proprio per tener conto di questa eventualità. Il nuovo stato iniziale è collegato ovviamente a quello vecchio di N'_1_' da una solita freccia ε.\\ to:
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'_1_' 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'_1_' a quello iniziale di N'_1_', 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'_1_' da una solita freccia ε.\\ Changed line 217 from:
La costruzione di N=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_1_''',''F'_1_''') che riconosce lo star del linguaggio A'_1_' va fatta così: to:
La costruzione di N=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_0_''',''F'_1_''') che riconosce lo star del linguaggio A'_1_' va fatta così: Changed line 222 from:
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia: to:
# definiamo la δ in modo che per q∈Q e ''a''∈Σ'_ε_' si abbia:
Changed line 90 from:
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'_0_''',''F'') che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=('Q9''',''Σ''',''δ''',''q'_0_'''',''F''') che riconosca A.\\ to:
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'_0_',F) che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(Q',Σ',δ',q'_0_'' ,F') che riconosca A.\\
Changed line 78 from:
# 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_'); to:
# 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_');
Changed line 77 from:
# r'_0_' = q'_0_' (la macchina parte dalle stato iniziale); to:
# r'_0_' = q'_0_' (la macchina parte dallo stato iniziale);
Changed lines 51-52 from:
(:cellnr bgcolor=#f5f9fc align=center:)1
(:cellnr bgcolor=#f5f9fc align=center:)ε to:
(:cell bgcolor=#f5f9fc align=center:)1
(:cell bgcolor=#f5f9fc align=center:)ε
Added lines 1-227:
(:title Informatica Teorica - Nondeterminismo :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Nondeterminismo ::'''
%center% %sottotitolo% Appunti & Dimostrazioni del 17 Marzo
>>frame<<
Le immagini di questa pagina sono prese dalle slide della prof [[Trucco->GTrucco]]
>><<
!!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 ci troviamo su uno stato della copia della macchina, e il prossimo simbolo che gli si vuole passare non si trova su nessuna delle sue frecce uscenti, si abbandona tutto il ramo della computazione che porta fino a lui;
* se almeno una delle copie raggiunge al termine della computazione lo stato finale, 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:
%center%Attach:IT-nfaEs1.gif
Ecco l'albero di computazione corrispondente per la stringa di ingresso [@010110@]:
%center%Attach:IT-nfaEs2.gif
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@] se si è nello stato ''q'_2_''', e [@11@] se siamo nello stato ''q'_3_'''.
!!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 ε.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un automa a stati finiti non deterministico è una 5-tupla (''Q'', ''Σ'', ''δ'', ''q'_0_''', ''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'_0_' ∈ 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'_1_', q'_2_', q'_3_', q'_4_'}
->2. Σ = {0,1}
->3. δ è dato da:
(:table align=center width=40%:)
(:cellnr bgcolor=#f5f9fc align=center:)
(:cell bgcolor=#f5f9fc align=center:)0
(:cellnr bgcolor=#f5f9fc align=center:)1
(:cellnr bgcolor=#f5f9fc align=center:)ε
(:cellnr bgcolor=#f5f9fc align=center:)q'_1_'
(:cell align=center:){q'_1_'}
(:cell align=center:){q'_1_',q'_2_'}
(:cell align=center:)0
(:cellnr bgcolor=#f5f9fc align=center:)q'_2_'
(:cell align=center:){q'_3_'}
(:cell align=center:)0
(:cell align=center:){q'_3_'}
(:cellnr bgcolor=#f5f9fc align=center:)q'_3_'
(:cell align=center:)0
(:cell align=center:){q'_4_'}
(:cell align=center:)0
(:cellnr bgcolor=#f5f9fc align=center:)q'_4_'
(:cell align=center:){q'_4_'}
(:cell align=center:){q'_4_'}
(:cell align=center:)0
(:tableend:)
->4. q'_1_' è lo stato di partenza
->5. F = {q'_4_'}
!!!Definizione formale di computazione
Sia dato un automa [@n.d.@] N=(''Q'',''Σ'',''δ'',''q'_0_''',''F''), ed una stringa di ingresso w tale che w = y'_1_'y'_2_'..y'_m_' , dove ogni y'_i_' fa parte dell'alfabeto Σ'_ε_'.\\
Diciamo che N '''accetta''' w se esiste una sequenza di stati r'_0_'r'_1_'..r'_m_' in Q che rispettino tre condizioni:
# r'_0_' = q'_0_' (la macchina parte dalle 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? E a cosa servono i teoremi?
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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'_0_''',''F'') che supponiamo riconosca il linguaggio A, vogliamo creare il corrispondente automa deterministico M=(''Q9''',''Σ''',''δ''',''q'_0_'''',''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. Per ogni caso dovremo specificare come vanno messi in corrispondenza i vari elementi della quintupla.
''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'_0_'' = {q'_0_'}\\
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 ∈ δ(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'_0_'' = {q'_0_'}\\
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:
%center%Attach:IT-nfa2dfa-1.gif
Ecco il DFA corrispondente:
%center%Attach:IT-nfa2dfa-2.gif
!!!Corollario al Teorema 1
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
La classe di linguaggi regolari è chiusa rispetto all'operazione di unione.
>><<
'''Dimostrazione'''
Abbiamo due linguaggi A'_1_' e A'_2_' e vogliamo dimostrare che la loro unione è regolare. L'idea è quella di prendere due automi [@n.d.@] N'_1_' ed N'_2_' 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:
%center%Attach:IT-chiusUn.gif
Più formalmente, siano dati due automi [@n.d.@]:
* N'_1_'=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_1_''',''F'_1_''') che riconosce il linguaggio A'_1_';
* N'_2_'=(''Q'_2_''',''Σ'',''δ'_2_''',''q'_2_''',''F'_2_''') che riconosce il linguaggio A'_2_'.
La costruzione di N=(''Q'',''Σ'',''δ'',''q'_0_''',''F'') che riconosce l'unione dei linguaggi A'_1_' e A'_2_' va fatta così:
# Q = {q'_0_'} U Q'_1_' U Q'_2_'\\
Gli stati di N sono tutti quelli di N'_1_' più quelli di N'_2_' più il nuovo stato iniziale q'_0_'
# Σ non cambia
# q'_0_' è il nuovo stato iniziale
# F = F'_1_' U F'_2_'\\
N accetta se o N'_1_' o N'_2_' accettano
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia:
%center%Attach:IT-chiusUn-transiz.gif
!!!Teorema 3 - sulla chiusura rispetto l'operazione di concatenazione
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
La classe di linguaggi regolari è chiusa rispetto all'operazione di concatenazione.
>><<
'''Dimostrazione'''
Abbiamo due linguaggi A'_1_' e A'_2_' e vogliamo dimostrare che la loro concatenazione è regolare. L'idea è quella di prendere due automi [@n.d.@] N'_1_' ed N'_2_' 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'_1_', quindi i due riconosceranno le stesse stringhe di ingresso;
* gli stati finali di N'_1_' vanno collegati a quello iniziale di N'_2_' con frecce ε;
* lo stato finale di N deve corrispondere a quello di N'_2_'.
Anche in questo caso si capisce meglio in figura:
%center%Attach:IT-chiusCo.gif
Più formalmente, siano dati due automi [@n.d.@]:
* N'_1_'=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_1_''',''F'_1_''') che riconosce il linguaggio A'_1_';
* N'_2_'=(''Q'_2_''',''Σ'',''δ'_2_''',''q'_2_''',''F'_2_''') che riconosce il linguaggio A'_2_'.
La costruzione di N=(''Q'',''Σ'',''δ'',''q'_1_''',''F'_2_''') che riconosce la concatenazione dei linguaggi A'_1_' e A'_2_' va fatta così:
# Q = Q'_1_' U Q'_2_'\\
Gli stati di N sono tutti quelli di N'_1_' più quelli di N'_2_'
# Σ non cambia
# q'_1_' è lo stato iniziale
# F'_2_' è l'insieme degli stati finali
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia:
%center%Attach:IT-chiusCo-transiz.gif
!!!Teorema 4 - sulla chiusura rispetto l'operazione di star
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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 (ringraziatemi).\\
Abbiamo un linguaggio A e vogliamo dimostrare che il suo star A* è regolare. L'idea è quella di prendere l'automa [@n.d.@] N'_1_' 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'_1_' a quello iniziale di N'_1_', 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 anche essere vuota: la ripetizione di una stringa vuota sarebbe una stringa vuota, quindi lo stato iniziale di N dovrebbe essere anche uno di quelli finali, proprio per tener conto di questa eventualità. Il nuovo stato iniziale è collegato ovviamente a quello vecchio di N'_1_' da una solita freccia ε.\\
Vediamo in figura:
%center%Attach:IT-chiusSt.gif
Più formalmente, sia dato l'automa [@n.d.@]:
* N'_1_'=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_1_''',''F'_1_''') che riconosce il linguaggio A'_1_'.
La costruzione di N=(''Q'_1_''',''Σ'',''δ'_1_''',''q'_1_''',''F'_1_''') che riconosce lo star del linguaggio A'_1_' va fatta così:
# Q = {q'_0_'} U Q'_1_'
# Σ non cambia
# q'_0_' è il nuovo stato iniziale
# F = {q'_0_'} U F'_1_'
# definiamo la δ in modo che per q⊆Q e ''a''⊆Σ'_ε_' si abbia:
%center%Attach:IT-chiusSt-transiz.gif
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
