Convertire un NFA in un DFA
Dato un automa a stati finiti non deterministico,
ad esempio l'automa :
$A={Q,I,sigma,q0,F}$
Q:insieme di stati
I:insieme di input {0,1}
$sigma$:QxI->Q
q0:stato inziale
F:Insieme degli stati acettanti {q1,q2}
Per converirlo in un DFA come procedo?
ad esempio l'automa :
$A={Q,I,sigma,q0,F}$
Q:insieme di stati
I:insieme di input {0,1}
$sigma$:QxI->Q
q0:stato inziale
F:Insieme degli stati acettanti {q1,q2}
Per converirlo in un DFA come procedo?
Risposte
Non è difficile, guarda per esempio su queste note a cura di Luca Tesei (mi sembrano molto ben fatte, del resto dice in parte le ha tratte dal classico Aho-Sethi-Ullman)
http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf
[ PS. Ne approfitto: altre sezioni hanno un argomento "top" dedicato a Dispense ed Appunti disponibili sul web, non è che si può inserire anche qui..? ]
http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf
[ PS. Ne approfitto: altre sezioni hanno un argomento "top" dedicato a Dispense ed Appunti disponibili sul web, non è che si può inserire anche qui..? ]
manca l'etichetta dal q3 a q1 che sarebbe 1;
per creare il DFA devo partire dalla tabella delle transazioni:
a questo punto come procedo?
per creare il DFA devo partire dalla tabella delle transazioni:
a questo punto come procedo?
Ehm.. ti è chiaro il procedimento? Sembra di no: difatti non capisco a cosa servano tutti quegli stati fittizzi (o ti è stato spiegato in quel modo?) A me viene un DFA semplicissimo.
Allora, partendo dallo stato iniziale del NFA trova gli insiemi di stati raggiungibili con i possibili input:
- da q0 con input '0' puoi raggiungere q1 e q2, quindi uno stato che è l'unione di questi: {q1, q2}
- da q0 con input '1': idem.
Hai adesso un 'nuovo' stato {q1, q2}. Devi trovare gli insiemi di stati raggiungibili con i possibili input:
- da {q1, q2} con input '0', che equivale a dire "da q1 con input '0' o da q2 con input '0'", posso raggiungere q1, q2 e q3, quindi uno stato che è l'unione di questi: {q1, q2, q3};
- da {q1, q2} con input '1' -> prova te a completare.
Poi marchi gli stati finali; quali sono lo sai, giusto?
Allora, partendo dallo stato iniziale del NFA trova gli insiemi di stati raggiungibili con i possibili input:
- da q0 con input '0' puoi raggiungere q1 e q2, quindi uno stato che è l'unione di questi: {q1, q2}
- da q0 con input '1': idem.
Hai adesso un 'nuovo' stato {q1, q2}. Devi trovare gli insiemi di stati raggiungibili con i possibili input:
- da {q1, q2} con input '0', che equivale a dire "da q1 con input '0' o da q2 con input '0'", posso raggiungere q1, q2 e q3, quindi uno stato che è l'unione di questi: {q1, q2, q3};
- da {q1, q2} con input '1' -> prova te a completare.
Poi marchi gli stati finali; quali sono lo sai, giusto?
allora seguendo dallo stato q0 e considerando solo gli stati che raggingo trovo:
Visto? Non era difficile. Ed ora puoi semplificare l'automa (che accetta qualunque stringa di zero e uno. 
)
Per i moderatori: ripropongo ancora la creazione di un thread ad-hoc che raccolga segnalazioni di dispense ed appunti reperibili sul web.
)Per i moderatori: ripropongo ancora la creazione di un thread ad-hoc che raccolga segnalazioni di dispense ed appunti reperibili sul web.
con il seguente $epsilon$-NFA:
che ha come transazione ECLOSE:
$ECLOSE(q0)={q0,q1}$
$ECLOSE(q1)={q1}$
$ECLOSE(q2)={q2,q3,q4}$
$ECLOSE(q3)={q3,q4}$
$ECLOSE(q4)={q4}$
come lo converto in un DFA?
che ha come transazione ECLOSE:
$ECLOSE(q0)={q0,q1}$
$ECLOSE(q1)={q1}$
$ECLOSE(q2)={q2,q3,q4}$
$ECLOSE(q3)={q3,q4}$
$ECLOSE(q4)={q4}$
come lo converto in un DFA?
[La epsilon-chiusura non è una "transazione"]
La conversione si fa nella stessa identica maniera vista prima, ma poichè il tuo automa ha anche transizioni con la stringa vuota (detta anche nulla, epsilon $epsilon$, lambda $lambda$...), il raggruppamento viene fatto considerando anche lo stato di partenza della transizione stessa.
La $epsilon$-chiusura ti indica quali stati sono raggruppabili considerando anche la stringa vuota. Rivediti il link che ti ho postato prima, prova a risolvere e posta il tuo risultato che lo commentiamo assieme.
La conversione si fa nella stessa identica maniera vista prima, ma poichè il tuo automa ha anche transizioni con la stringa vuota (detta anche nulla, epsilon $epsilon$, lambda $lambda$...), il raggruppamento viene fatto considerando anche lo stato di partenza della transizione stessa.
La $epsilon$-chiusura ti indica quali stati sono raggruppabili considerando anche la stringa vuota. Rivediti il link che ti ho postato prima, prova a risolvere e posta il tuo risultato che lo commentiamo assieme.
allora per convertirlo procedo come ho visto a lezione:
parto dagli stati dell'ecloce di q0;
$Eclose(q0)={q0,q1}$ che chiamo p1;
$p1={q0,q1}$ con input A,B vado in ${q1,q2}$ ora facciao l'Eclose di questi stati $Eclose(q1,q2)={q1,q2,q3,q4}$*, che è un nuovo stato che chiamo p2
da p1 con input 0..9 non vado in nessuono stato
$p2={q1,q2,q3,q4}$* con A,B vado in ${q2}$ la cui funzione eclose genera ${q2,q3,q4}$* che chiamo p3
da p2 con 0..9 vado in ${q3,q4}$ che ha eclose ${q3,q4}$* che chiamo p4
$p3={q2,q3,q4}$* con A,B è vuoto
con 0..9 vado in q4 la cui eclose è ${q4}$* che chiamo p5
$p4={q3,q4}$*
con 0..9 vado in q4 che ha per eclose q4 cioè lo stato p5
quindi ho:
p1 raggiungo p2 con etichetta A o B
p2 raggingo p3 con A o B, da p2 raggingo p4 con 0..9
p3 raggiungo con 0..9 p5
p4 raggiungo con 0..9 p5
parto dagli stati dell'ecloce di q0;
$Eclose(q0)={q0,q1}$ che chiamo p1;
$p1={q0,q1}$ con input A,B vado in ${q1,q2}$ ora facciao l'Eclose di questi stati $Eclose(q1,q2)={q1,q2,q3,q4}$*, che è un nuovo stato che chiamo p2
da p1 con input 0..9 non vado in nessuono stato
$p2={q1,q2,q3,q4}$* con A,B vado in ${q2}$ la cui funzione eclose genera ${q2,q3,q4}$* che chiamo p3
da p2 con 0..9 vado in ${q3,q4}$ che ha eclose ${q3,q4}$* che chiamo p4
$p3={q2,q3,q4}$* con A,B è vuoto
con 0..9 vado in q4 la cui eclose è ${q4}$* che chiamo p5
$p4={q3,q4}$*
con 0..9 vado in q4 che ha per eclose q4 cioè lo stato p5
quindi ho:
p1 raggiungo p2 con etichetta A o B
p2 raggingo p3 con A o B, da p2 raggingo p4 con 0..9
p3 raggiungo con 0..9 p5
p4 raggiungo con 0..9 p5
Olè!
E ottieni un DFA che accetta le stringhe che cominciano per A o B sul tuo alfabeto, ovvero anche stavolta semplificabile: prova a fare il DFA minimo equivalente, se hai difficoltà considera che accetta la seguente regex:
(A|B)[AB0-9]*
[ Noto che usi JFLAP, quindi per il futuro non dovresti più avere problemi. ]
E ottieni un DFA che accetta le stringhe che cominciano per A o B sul tuo alfabeto, ovvero anche stavolta semplificabile: prova a fare il DFA minimo equivalente, se hai difficoltà considera che accetta la seguente regex:
(A|B)[AB0-9]*
[ Noto che usi JFLAP, quindi per il futuro non dovresti più avere problemi. ]
immagino che l'automa minimo sia
"BHK":
con il seguente $epsilon$-NFA:
che ha come transazione ECLOSE:
$ECLOSE(q0)={q0,q1}$
$ECLOSE(q1)={q1}$
$ECLOSE(q2)={q2,q3,q4}$
$ECLOSE(q3)={q3,q4}$
$ECLOSE(q4)={q4}$
come lo converto in un DFA?
"Rggb":
Olè!
E ottieni un DFA che accetta le stringhe che cominciano per A o B sul tuo alfabeto, ovvero anche stavolta semplificabile: prova a fare il DFA minimo equivalente, se hai difficoltà considera che accetta la seguente regex:
(A|B)[AB0-9]*
[ Noto che usi JFLAP, quindi per il futuro non dovresti più avere problemi. ]
L'NFA in questione non riconosce le cifre [0-9] solamente se presenti da 0 a 2 volte?
E' corretto mettere quindi [0-9]*?
In conclusione la soluzione che propongo è: (A|B)+ ([0-9][0-9] | [0-9] | stringa vuota)
Per la seconda parentesi penso esista una simbologia più adatta ma non la ricordo ora.
mi sono accorto che la conversione è sbagliata,
allora ricapitolando:
$ECLOSE(q0)={q0,q1}$
$ECLOSE(q1)={q1}$
$ECLOSE(q2)={q2,q3,q4}$
$ECLOSE(q3)={q3,q4}$
$ECLOSE(q4)={q4}$
P1=${q0,q1}$
Da P1 con A,B =${q1,q2} =ECLOSE(q1,q2)={q1,q2,q3,q4}$* nuovo stato che chiamo P2
Da P1 con 0..9 =${O/}$
Da P2 con A,B =${q1,q2}= ECLOSE(q1,q2)={q1,q2,q3,q4}$* quindi restiamo in P2
Da P2 con 0..9 =${q3,q4}= ECLOSE(q3,q4)={q3,q4}$* nuovo stato che chiamo P3
Da P3 con A,B =${O/}
Da P3 con 0..9 =${q4}= ECLOSE(q4)={q4}$* nuovo stato che chiamiamo P4
PS:la scrittura 0..9 è la forma compatta di (1,2,3,4,5,6,7,8,9)
Quindi per tornare alla domanda di hee136, si accetta stringhe che iniziano per A o B che contengono un qualsiasi numero di A o B e possono finire con al massimo due cifre (da 0 a 9).
allora ricapitolando:
$ECLOSE(q0)={q0,q1}$
$ECLOSE(q1)={q1}$
$ECLOSE(q2)={q2,q3,q4}$
$ECLOSE(q3)={q3,q4}$
$ECLOSE(q4)={q4}$
P1=${q0,q1}$
Da P1 con A,B =${q1,q2} =ECLOSE(q1,q2)={q1,q2,q3,q4}$* nuovo stato che chiamo P2
Da P1 con 0..9 =${O/}$
Da P2 con A,B =${q1,q2}= ECLOSE(q1,q2)={q1,q2,q3,q4}$* quindi restiamo in P2
Da P2 con 0..9 =${q3,q4}= ECLOSE(q3,q4)={q3,q4}$* nuovo stato che chiamo P3
Da P3 con A,B =${O/}
Da P3 con 0..9 =${q4}= ECLOSE(q4)={q4}$* nuovo stato che chiamiamo P4
PS:la scrittura 0..9 è la forma compatta di (1,2,3,4,5,6,7,8,9)
Quindi per tornare alla domanda di hee136, si accetta stringhe che iniziano per A o B che contengono un qualsiasi numero di A o B e possono finire con al massimo due cifre (da 0 a 9).
"hee136":
L'NFA in questione non riconosce le cifre [0-9] solamente se presenti da 0 a 2 volte?
No. Esempio: stringa "$A0$",
- da q0 a q1 con "$epsilon$";
- da q1 a q2 con "$A$";
- da q2 a q3 con "$epsilon$";
- da q3 a q4 con "$0$";
- q4 stato finale = stringa accettata.
"hee136":
E' corretto mettere quindi [0-9]*?
EDIT
La regex che ho indicato non è corretta (vedi più avanti), ma è corretto mettere [0-9]*
"BHK":
mi sono accorto che la conversione è sbagliata
Vedo, nemmeno io me ne sono accorto
In pratica (prima soluzione) ci siamo "scordati" di q2 nel calcolare gli stati di destinazione da p1; non me ne sono accorto perché il risultato è un automa equivalente."BHK":
Quindi per tornare alla domanda di hee136, si accetta stringhe che iniziano per A o B che contengono un qualsiasi numero di A o B e possono finire con al massimo due cifre (da 0 a 9).
No: vedi sopra.
allora tu hai scritto l'espressione regolare (A|B)[AB0-9]* che per esempio può generare: BAB0AB0 che non è accettata.
"BHK":
allora tu hai scritto l'espressione regolare (A|B)[AB0-9]* che per esempio può generare: BAB0AB0 che non è accettata.
Si vede che ho la febbre, che non mi accorgo di nulla
Difatti non può finire per 'A' o 'B'. Quindi:(A|B)[AB]*[0-9]*
Ovviamente cambia anche l'automa minimo.
"Rggb":
[quote="BHK"]allora tu hai scritto l'espressione regolare (A|B)[AB0-9]* che per esempio può generare: BAB0AB0 che non è accettata.
Si vede che ho la febbre, che non mi accorgo di nulla
Difatti non può finire per 'A' o 'B'. Quindi:(A|B)[AB]*[0-9]*
Ovviamente cambia anche l'automa minimo.[/quote]
Questo perchè il controllo che esegue l'automa è $ S nn F != O/ $ ?
$ S $ = insieme stati raggiunti
$ F $ = insieme stati finali
Non ho capito la domanda, che vorresti dire con "il controllo che esegue l'automa"?
Comunque risponderei "perché è così che l'automa è definito", questo riconosce il linguaggio regolare corrispondente alla regex:
(A|B)[AB]*[0-9]*
oppure - è equivalente, più sintetica
[AB]+[0-9]*
PS. L'automa minimo si ricava facilmente dall'ultimo illustrato da BHK, senza lo stato p4 e con un arco di transizione da p3 in se stesso per i simboli accettati '0'..'9'.
Comunque risponderei "perché è così che l'automa è definito", questo riconosce il linguaggio regolare corrispondente alla regex:
(A|B)[AB]*[0-9]*
oppure - è equivalente, più sintetica
[AB]+[0-9]*
PS. L'automa minimo si ricava facilmente dall'ultimo illustrato da BHK, senza lo stato p4 e con un arco di transizione da p3 in se stesso per i simboli accettati '0'..'9'.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo