Automa non deterministico
Sia L1 il linguaggio su alfabeto= {a,b} delle parole di lunghezza dispari che terminano per aba
1) anche la stringa aba puo' essere accettata?
2)ho definito il seguente automa
Uploaded with ImageShack.us
è corretto?
3)come creo il DFA?
1) anche la stringa aba puo' essere accettata?
2)ho definito il seguente automa
Uploaded with ImageShack.us
è corretto?
3)come creo il DFA?
Risposte
La risposta alla domanda (1) è sì: 'aba' è di lunghezza dispari e termina per 'aba'.
Non capisco il perché dei due stati 5 e 6. Comunque per esempio la stringa di lunghezza 6 "abaaba" è accettata...
Per il DFA puoi procedere dal NFA (corretto) e convertirlo; in alternativa puoi costruirlo direttamente, è abbastanza semplice.
Non capisco il perché dei due stati 5 e 6. Comunque per esempio la stringa di lunghezza 6 "abaaba" è accettata...
Per il DFA puoi procedere dal NFA (corretto) e convertirlo; in alternativa puoi costruirlo direttamente, è abbastanza semplice.
effettivamente ora che me lo hai fatto notare non so nemmeno io il perche' di quei 2 stati.....
dalla definizione secondo te sono vincolato a creare un epsilon-nfa?
suggerimenti per crearlo?ho dei problemi sul fatto che deve essere una stringa dispari....
dalla definizione secondo te sono vincolato a creare un epsilon-nfa?
suggerimenti per crearlo?ho dei problemi sul fatto che deve essere una stringa dispari....
Come hai giustamente impostato, la stringa da riconoscere 'aba' termina nello stato finale - quindi hai qualcosa del genere
da questo considera che nello stato iniziale "i" la stringa ha lunghezza pari (lunga 0, 2...), nel primo stato intermedio ha lunghezza dispari e così via, quindi devi aggiungere solo le transizioni da questi nello stato corretto. Prova e fammi sapere.
da questo considera che nello stato iniziale "i" la stringa ha lunghezza pari (lunga 0, 2...), nel primo stato intermedio ha lunghezza dispari e così via, quindi devi aggiungere solo le transizioni da questi nello stato corretto. Prova e fammi sapere.
e ora come faccio il dfa...è la epsilon transazione che mi disturba....
illuminami
Puoi semplificare il tuo NFA, evita di fare due rami separati per il riconoscimento di 'aba': togli il ramo sopra e metti la $\epsilon$-transizione da stato iniziale 0 a stato 6, ti torna?
Per il DFA puoi fare in due modi:
1) converti il NFA in DFA (conosci un algoritmo? Probabilmente è spiegato nel libro di testo/appunti/dispense che usi);
2) prendi il "pezzo" che ho messo sopra [che è equivalente al tuo, stati 6-7-8-9] e a questo aggiungi le transizioni mancanti: dallo stato iniziale $i$ manca 'b', dallo stato $x$ manca 'a', eccetera; aggiungi uno stato che conti un numero di caratteri dispari prima di 'aba' [considera che esiste già lo stato che conta il numero di caratteri pari, ed è lo stato iniziale] ed hai finito.
E' più semplice di quel che pensi, provaci. Lascio quello che ho definito io, in spoiler.
Per il DFA puoi fare in due modi:
1) converti il NFA in DFA (conosci un algoritmo? Probabilmente è spiegato nel libro di testo/appunti/dispense che usi);
2) prendi il "pezzo" che ho messo sopra [che è equivalente al tuo, stati 6-7-8-9] e a questo aggiungi le transizioni mancanti: dallo stato iniziale $i$ manca 'b', dallo stato $x$ manca 'a', eccetera; aggiungi uno stato che conti un numero di caratteri dispari prima di 'aba' [considera che esiste già lo stato che conta il numero di caratteri pari, ed è lo stato iniziale] ed hai finito.
E' più semplice di quel che pensi, provaci. Lascio quello che ho definito io, in spoiler.
Uploaded with ImageShack.us
per la conversione in dfa dimmi se ho fatto correttamente
eclose(0)={0,2}
eclose(1)={1}
eclose(2)={2}
eclose(3)={3}
eclose(4)={4}
eclose(5)={5}
a b
0,2 1,3 1
1 2 2
2 3
3 4
4 5
1,3 2 2,4
2,4 3,5
3,5 4
dfa
Mi sembra il procedimento vada bene - magari sii più preciso: ci sono tutte le transizioni? (mi pare di no)
Comunque semplificando ti dovrebbe venire: se dal tuo NFA corretto (di sopra) togli lo stato 0, vedrai funziona ugualmente (usando 2 come stato iniziale). Ti basta completare questo aggiungendo le opportune transizioni (viene uguale a quello che ho messo io).
Comunque semplificando ti dovrebbe venire: se dal tuo NFA corretto (di sopra) togli lo stato 0, vedrai funziona ugualmente (usando 2 come stato iniziale). Ti basta completare questo aggiungendo le opportune transizioni (viene uguale a quello che ho messo io).
Uploaded with ImageShack.us
6 un grande ora il DFA è venuto come il tuo con gli altri archi che mancavano.............grazieeeeeeeeeeeeeee
ma è sempre possibile da un epsilon-nfa a nfa? o questo è un caso favorevole?io vado in difficolta quando ci sono gli epsilon
è corretto dire che questo automa è minimale perche' tutti gli stati sono accessibili e perche' tutti gli stati possono raggiungere lo stato finale?
ora voglio scrivere la RE....
((a+b)(a+b))*(a+b) + aba
è giusta?
sia L2 il linguaggio su alfabeto {a,b} delle parole di lunghezza pari che iniziano per aba e NON terminano per aba....
guarda che ho creato
Uploaded with ImageShack.us
è giusto?è possibile semplificarlo?
guarda che ho creato
Uploaded with ImageShack.us
è giusto?è possibile semplificarlo?
Mi sembra a posto ma magari controlla con JFLAP. Mi viene un DFA (completo, minimo) così
(mancano solo le transizioni dallo stato X: per qualunque input, l'automa rimane in X).
Se prendi il tuo, lo converti in deterministico e lo minimizzi, dovrebbe venirti un automa equivalente, puoi usare JFLAP per farlo. Prova e fammi sapere.
(mancano solo le transizioni dallo stato X: per qualunque input, l'automa rimane in X).
Se prendi il tuo, lo converti in deterministico e lo minimizzi, dovrebbe venirti un automa equivalente, puoi usare JFLAP per farlo. Prova e fammi sapere.
Grazie mille ho risolto...alla prossima
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo