Automi NFA e DFA
Salve a tutti, sono uno studente di informatica al primo anno e ho da poco iniziato programmazione. Ho alcuni dubbi su come costruire degli automi, ad esempio:
partendo da un linguaggio L espresso con la specifica formale generica quali sono i passi da fare per creare un automa NFA o DFA? Come creare un e-NFA l'ho capito, devo partire da quello? Come? Un grazie in anticipo!
partendo da un linguaggio L espresso con la specifica formale generica quali sono i passi da fare per creare un automa NFA o DFA? Come creare un e-NFA l'ho capito, devo partire da quello? Come? Un grazie in anticipo!
Risposte
Non mi è chiaro... partendo da un linguaggio regolare? Anche la "specifica formale generica" per me non ha molto senso. E poi: e-NFA cosa intendi, NFA con transizioni vuote (o nulle, o con stringa nulla, o che dir si voglia)?
Magari metti un esempio di cosa ti servirebbe.
Magari metti un esempio di cosa ti servirebbe.
Si, con e-NFA intendo un automa epsilon-NFA, cioè un automa non deterministico che accetti anche stringhe vuote. In pratica gli esercizi mi chiedono di creare un automa sulla base di un linguaggio che mi viene dato. Faccio un esempio:
"Dati i seguenti linguaggi L1 = {$a^n$$b^m$c |n $>-$ 0 ,m $>=$ 0} e L2 = {$a^n$s | n $>-$ 3, s $in$ L1} si costruisca una NFA o DFA che accetti il linguaggio L = L1 $uuu$ L2"
"Dati i seguenti linguaggi L1 = {$a^n$$b^m$c |n $>-$ 0 ,m $>=$ 0} e L2 = {$a^n$s | n $>-$ 3, s $in$ L1} si costruisca una NFA o DFA che accetti il linguaggio L = L1 $uuu$ L2"
Ciao, riprendo l'argomento solo ora perché ero "fuori stanza"... 
Certo, se sai come costruire un e-NFA puoi sempre fare un NFA o DFA equivalente, vi sono degli algoritmi che puoi trovare sul tuo libro di testo e/o appunti del/la prof.
Mi viene un automa DFA con 9 stati, con la seguente funzione di transizione, rappresentata da una tabella.
S a b c
0 1 8 8
1 4 2 3
2 8 2 3
3 8 8 8
4 5 8 2
5 6 2 8
6 7 2 8
7 7 2 8
8 8 8 8
Stato iniziale 0, finale 3 - spero di non aver ricopiato male, al limite rifai tu l'esercizio e mi correggi. Non ho verificato se è minimo (non mi sembra). Ovviamente puoi anche fare un e-NFA e poi trasformarlo, come dicevo prima.
Comunque, ti consiglio di usare JFLAP:
http://www.cs.duke.edu/csed/jflap/
un utile strumento per capire queste cose, ed altro, e utilissimo per gli esercizi.
Certo, se sai come costruire un e-NFA puoi sempre fare un NFA o DFA equivalente, vi sono degli algoritmi che puoi trovare sul tuo libro di testo e/o appunti del/la prof.
"Nepenthe":
"Dati i seguenti linguaggi L1 = {$a^n$$b^m$c |n $>-$ 0 ,m $>=$ 0} e L2 = {$a^n$s | n $>-$ 3, s $in$ L1} si costruisca una NFA o DFA che accetti il linguaggio L = L1 $uuu$ L2"
Mi viene un automa DFA con 9 stati, con la seguente funzione di transizione, rappresentata da una tabella.
S a b c
0 1 8 8
1 4 2 3
2 8 2 3
3 8 8 8
4 5 8 2
5 6 2 8
6 7 2 8
7 7 2 8
8 8 8 8
Stato iniziale 0, finale 3 - spero di non aver ricopiato male, al limite rifai tu l'esercizio e mi correggi. Non ho verificato se è minimo (non mi sembra). Ovviamente puoi anche fare un e-NFA e poi trasformarlo, come dicevo prima.
Comunque, ti consiglio di usare JFLAP:
http://www.cs.duke.edu/csed/jflap/
un utile strumento per capire queste cose, ed altro, e utilissimo per gli esercizi.
Grazie mille Rggb, con il DFA ci siamo, ho trovato l'algoritmo che dicevi. Ma nel caso volessi trasformare un e-NFA in un NFA? Questo è il vero problema... Innanzitutto è possibile o bisogna passare per il DFA?
E' certamente possibile, anche se personalmente non ho mai applicato il metodo: tieni presente che io considero NFA ed e-NFA la stessa cosa, ovvero un automa non deterministico.
Il sistema è semplice, crei un automa che ha come nuovi stati l'unione degli stati "epsilon-raggiungibili" e ricalcoli da questi le nuove transizioni sulla base delle precedenti:
- il nuovo stato iniziale 0 del NFA (senza e-regole) è: lo stato iniziale del e-NFA più tutti gli stati raggiungibili da questo con transizioni vuote (epsilon-transizioni);
- il nuovo stato 1 del NFA è: lo stato 1 del e-NFA più tutti gli stati raggiungibili da questo con transizioni vuote;
eccetera. Le funzioni di transizione del nuovo automa sono calcolate su tutti gli stati così raggruppati.
Ma strano... non hai trovato nulla su Internet?!? Cercando qualche minuto ho trovato decine di esempi, fra l'altro chiarissimi per comprendere il metodo.
Il sistema è semplice, crei un automa che ha come nuovi stati l'unione degli stati "epsilon-raggiungibili" e ricalcoli da questi le nuove transizioni sulla base delle precedenti:
- il nuovo stato iniziale 0 del NFA (senza e-regole) è: lo stato iniziale del e-NFA più tutti gli stati raggiungibili da questo con transizioni vuote (epsilon-transizioni);
- il nuovo stato 1 del NFA è: lo stato 1 del e-NFA più tutti gli stati raggiungibili da questo con transizioni vuote;
eccetera. Le funzioni di transizione del nuovo automa sono calcolate su tutti gli stati così raggruppati.
Ma strano... non hai trovato nulla su Internet?!? Cercando qualche minuto ho trovato decine di esempi, fra l'altro chiarissimi per comprendere il metodo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo