Linguaggi&Traduttori da espressione regolare ad automa N
Salve a tutti, sono nuovo del forum e vorrei innanzitutto farvi i complimenti!!!
Arrivo subito al dunque...Il mio problema è il seguente: sto preparando l'esame di linguaggi e traduttori e mi sono imbattuto nelle espressioni regolari. Non riesco a capire come procedere quando mi viene chiesto di determinare l'automa corrispondente ad una espressione regolare. Ho passato due ore a costruire l'automa deterministico per l'espressione (b*a(a*|b)a*b)* ovviamente senza risultati! La soluzione mi mostra un automa NFA
Allora mi chiedo, esiste un modo per capire dall'espressione regolare se bisogna costruire un automa deterministico o uno non (con epsilon produzioni) ? Vi ringrazio in anticipo!!!
Arrivo subito al dunque...Il mio problema è il seguente: sto preparando l'esame di linguaggi e traduttori e mi sono imbattuto nelle espressioni regolari. Non riesco a capire come procedere quando mi viene chiesto di determinare l'automa corrispondente ad una espressione regolare. Ho passato due ore a costruire l'automa deterministico per l'espressione (b*a(a*|b)a*b)* ovviamente senza risultati! La soluzione mi mostra un automa NFA
Allora mi chiedo, esiste un modo per capire dall'espressione regolare se bisogna costruire un automa deterministico o uno non (con epsilon produzioni) ? Vi ringrazio in anticipo!!!
Risposte
Non ho ben capito: come fai a costruire l'automa dall'e.r.? Esiste un algoritmo preciso, che è poi quello che viene utilizzato nella dimostrazione del teorema di Kleene (almeno per come l'ho studiata io). Applicandolo ad un'e.r. qualsiasi ottieni un automa che non è detto sia deterministico. Se poi vuoi costruire un DFA esiste un altro algoritmo che ti permette di farlo a partire dal NFA corrispondente.
Grazie per la risposta. Io però volevo sapere se osservando un'espressione regolare fosse possibile capire che tipo di automa costruire (DFA o epsilon-NFA).
Entrambi. Il DFA è un caso particolare di NFA e dall'NFA puoi costuirti un DFA equivalente. Quindi non capisco proprio quale sia il senso di questa domanda.
Allora. Ho fatto questa domanda perchè gli esercizi di esame sono svolti sia con epsilon-NFA che con DFA e non capisco perchè in alcuni casi predilige i primi piuttosto che i secondi. So benissimo che cos'è un NFA e un DFA. E poi il teorema di Kleene prevede tre tesi da dimostrare con tre algoritmi: dalle grammatiche agli automi, dagli automi alle grammatiche e dagli automi alle ER. No dalle ER agli automi (che è quello chiedo io) 
Non so perchè gli esercizi siano svolti costruendo a volte un NFA e a volte un DFA. Tuttavia esiste un algoritmo per costruire l'epsilon-NFA a partire dalla e.r.. Lo conosci?
Costruito l'automa non deterministico se poi ti è richiesto puoi benissimo costruirti il DFA corrispondente.
EDIT: in effetti sulla dimostrazione del teorema di Kleene hai ragione tu: l'algoritmo non viene utilizzato, tuttavia il teorema afferma che è la costruzione di un automa equivalente all'e.r. è possibile.
Costruito l'automa non deterministico se poi ti è richiesto puoi benissimo costruirti il DFA corrispondente.
EDIT: in effetti sulla dimostrazione del teorema di Kleene hai ragione tu: l'algoritmo non viene utilizzato, tuttavia il teorema afferma che è la costruzione di un automa equivalente all'e.r. è possibile.
Ma scusa 
Se te lo sto chiedendo io questo algoritmo!!! 
Se te lo sto chiedendo io questo algoritmo!!!
Non mi era chiaro se lo conoscevi o no visto che la tua domanda era sull'automa ottenuto se deterministico o no e non capivo che senso avesse.
Comunque, l'algoritmo è questo: decomporre in blocchi l'espressione, costruire l'NFA che riconosce quel blocco (espressioni semplici hanno NFA semplici quindi non è difficile) e concatenare poi tramite epsilon-transizioni i vari blocchi.
Guarda l'es. 4 (e la spiegazione soprastante) di queste esercitazioni trovate sul web http://corsi.deis.unical.it/OLD/linguag ... ione3B.pdf
Comunque, l'algoritmo è questo: decomporre in blocchi l'espressione, costruire l'NFA che riconosce quel blocco (espressioni semplici hanno NFA semplici quindi non è difficile) e concatenare poi tramite epsilon-transizioni i vari blocchi.
Guarda l'es. 4 (e la spiegazione soprastante) di queste esercitazioni trovate sul web http://corsi.deis.unical.it/OLD/linguag ... ione3B.pdf
OK! Grazie! Ora mi sapresti dire quando si usa un epsilon-NFA piuttosto che un NFA?
"DandiDoc":
OK! Grazie! Ora mi sapresti dire quando si usa un epsilon-NFA piuttosto che un NFA?
Uhu? Che intendi "quando" si usa?
Quando hai un'espressione regolare, come fai a sapere se costruire un automa NFA piuttosto che un automa epsilon-NFA? C'è una qualche regola?
Non sempre un NFA riconosce una regex, mentre un NFA con transizioni vuote (nulle, epsilon-transizioni) sì.
PS. Qualcuno ti ha detto (o hai letto da qualche parte) di usare (costruire) un NFA invece di un e-NFA per le regex? Strano... forse per esercizio?
PS. Qualcuno ti ha detto (o hai letto da qualche parte) di usare (costruire) un NFA invece di un e-NFA per le regex? Strano... forse per esercizio?
Si tratta di esercizi presi da prove di esame in cui mi viene chiesto di determinare un automa data da una certa espressione regolare...a volte la soluzione consiste in NFA e a volte in e-NFA. Allora mi è venuto il dubbio se per caso ci fosse un qualche meccanismo con cui capire quale dei due è la soluzione migliore. Quindi se costruisco un e-NFA vado sempre sul sicuro, tanto lo devo convertire in DFA, vero? Ti ringrazio 
Ma non capisco: usi una procedura differente per costruire gli automi NFA (rigorosamente SEMPRE senza e-trans) ed epsilon-NFA? Credo di no; fra l'altro l'algoritmo è sempre il solito.
Come ti ha già spiegato Deckard, è un metodo semplice (ti ha postato un link, non l'ho letto ma sarà come gli altri che ci sono nei vari corsi universitari).
E quindi, direi siamo in presenza di un semplice "misunderstood", se come dici la soluzione "a volte è un e-NFA, a volte è un NFA"; non devi distinguere i due tipi (NFA da e-NFA): se costruisci un e-NFA che, guarda caso, non ha transizioni vuote, ottieni un NFA.
[nota: sarò fatto male ma io per l'automa del riconoscimento delle regex parto sempre prima dal DFA
]
Come ti ha già spiegato Deckard, è un metodo semplice (ti ha postato un link, non l'ho letto ma sarà come gli altri che ci sono nei vari corsi universitari).
E quindi, direi siamo in presenza di un semplice "misunderstood", se come dici la soluzione "a volte è un e-NFA, a volte è un NFA"; non devi distinguere i due tipi (NFA da e-NFA): se costruisci un e-NFA che, guarda caso, non ha transizioni vuote, ottieni un NFA.
[nota: sarò fatto male ma io per l'automa del riconoscimento delle regex parto sempre prima dal DFA
]
Scusami, ma come fai a partire sempre da un DFA? Ci sono casi in cui non è possibile...non per niente i grafo delle equivalenze relativo alla rappresentazione dei linguaggi regolari è questo http://img825.imageshack.us/img825/1033 ... a11105.png
[/img]
[/img]
Abbiamo chiarito il punto precedente, ovvero che non ha senso distinguere NFA da e-NFA.
Anzi, essi sono "equivalenti" nel senso che puoi sempre trasformare un NFA in un e-NFA e viceversa, e anche in un DFA. E quindi
questa affermazione sicuramente non è corretta. Infatti se hai una regex puoi sempre costruire il DFA che la riconosce.
Intendi forse dire che non riesci a costruirlo direttamente? Però questa è una cosa diversa.
Anzi, essi sono "equivalenti" nel senso che puoi sempre trasformare un NFA in un e-NFA e viceversa, e anche in un DFA. E quindi
"DandiDoc":
Scusami, ma come fai a partire sempre da un DFA? Ci sono casi in cui non è possibile...
questa affermazione sicuramente non è corretta. Infatti se hai una regex puoi sempre costruire il DFA che la riconosce.
Intendi forse dire che non riesci a costruirlo direttamente? Però questa è una cosa diversa.
Siccome odio assai 
questa materia ti prego di sopportare le mie domande 
"Indirettamente" perchè il DFA è l'ultimo automa che si potrebbe ottenere...non si è obbligati a passare da un NFA(o da un e-NFA)? Avevo solo risposto a quanto avevi scritto "[nota: sarò fatto male ma io per l'automa del riconoscimento delle regex parto sempre prima dal DFA ]"
questa materia ti prego di sopportare le mie domande "Indirettamente" perchè il DFA è l'ultimo automa che si potrebbe ottenere...non si è obbligati a passare da un NFA(o da un e-NFA)? Avevo solo risposto a quanto avevi scritto "[nota: sarò fatto male ma io per l'automa del riconoscimento delle regex parto sempre prima dal DFA ]"
"DandiDoc":
Siccome odio assai
Figurati
"DandiDoc":
"Indirettamente" perchè il DFA è l'ultimo automa che si potrebbe ottenere...non si è obbligati a passare da un NFA(o da un e-NFA)? Avevo solo risposto a quanto avevi scritto "[nota: sarò fatto male ma io per l'automa del riconoscimento delle regex parto sempre prima dal DFA ]"
Avevo capito, e no: non si è "obbligati a fare un NFA", ma normalmente si fa così perché questo è più semplice (ovvero in generale ha meno stati/transizioni del DFA).
Io però trovo facile anche applicare prima il determinismo e poi semplificare l'automa ottenuto in un NFA. Boh, è questione di metodo.
PS. Per esercitarti, se già non lo hai, per queste materie ti consiglio ti usare JFLAP
http://www.cs.duke.edu/csed/jflap/
Ti ringrazio!!! Speriamo di riuscire a passare sto benedetto esame! Un saluto 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
