Espressini regolari e automi
Dato l'automa:
Voglio definirne l'espressione regolare corrispondente quindi il linguaggio accettato dall'automa.
Non ho ben capito il metodo canonico di costruzione.
Voglio definirne l'espressione regolare corrispondente quindi il linguaggio accettato dall'automa.
Non ho ben capito il metodo canonico di costruzione.
Risposte
Il tuo automa accetta il linguaggio dato da:
un numero qualsiasi di 1, seguito da uno 0, seguito da un un numero qualsiasi di 0 o di 1. (es.: "1111 0 101011001")
Quindi la RE associata è
1*0(0|1)*
dove | significa OR. Si indica anche con un "+".
un numero qualsiasi di 1, seguito da uno 0, seguito da un un numero qualsiasi di 0 o di 1. (es.: "1111 0 101011001")
Quindi la RE associata è
1*0(0|1)*
dove | significa OR. Si indica anche con un "+".
@Piz
Per quel che mi ricordo (ma potrei sbagliare, dopo controllo) usando la sintassi
(0|1)*
la regex corrisponde alle stringhe - eventualmente vuote - composte solo da caratteri '0' o '1', tipo 00000, 111, 00, 1111111, ... Infatti discorsivamente significa "zero oppure uno" x "qualsiasi numero di volte". Quindi magari è meglio
1*0[01]*
PS. Cosa vuoi dire con "si indica anche con +"?
Prima domanda: sai costruire la grammatica corrispondente al tuo automa?
Per quel che mi ricordo (ma potrei sbagliare, dopo controllo) usando la sintassi
(0|1)*
la regex corrisponde alle stringhe - eventualmente vuote - composte solo da caratteri '0' o '1', tipo 00000, 111, 00, 1111111, ... Infatti discorsivamente significa "zero oppure uno" x "qualsiasi numero di volte". Quindi magari è meglio
1*0[01]*
PS. Cosa vuoi dire con "si indica anche con +"?
"BHK":
Non ho ben capito il metodo canonico di costruzione.
Prima domanda: sai costruire la grammatica corrispondente al tuo automa?
No, allora posso intuire che tipo di espressioni accetta l'automa, ma non ho capito lo schema di costruzione delle espressioni regolari.
Le operazioni permesse sono l'unione insiemistica, la concatenazione e la chiusura di Kleene.
Le operazioni permesse sono l'unione insiemistica, la concatenazione e la chiusura di Kleene.
@Piz
Dunque ricontrollando, ho scoperto che la tua sintassi è corretta, e pure la mia
Uso normalmente le regex in cui le parentesi [] sono il raggruppamento.
@BHK
Per costruire le espressioni regolari si può usare un semplice algoritmo che trasforma il tuo automa (sotto forma di grafo disegnato come normalmente lo conosci, che è la cosa più intuitiva) nel grafo di espressione che contiene gli archi etichettati con espressioni regolari, che poi semplifichi con la tecnica di eliminazione degli stati.
Informalmente, pensa al cammino dallo stato iniziale del tuo automa verso il suo stato finale:
- sostituisci il simbolo '1' dell'arco da q1 in sé stesso (laccio) con l'espressione 1*
- togli il laccio
- aggiungi l'espressione trovata al successivo arco del cammino verso lo stato finale, ottenendo un arco con l'espressione '1*0'
- sostituisci i simboli '1' e '0' del laccio di q2 con l'espressione '(0|1)*' e togli il laccio
- aggiungi l'espressione all'unico arco dallo stato iniziale allo stato finale, ottenendo '1*0(0|1)*'
Se hai un automa con più stati finali e/o più cammini, le operazioni devono essere fatte per ogni cammino verso ogni stato finale.
Datti un'occhiata a queste slide che ti illustrano il procedimento, c'è anche un esempio:
http://www.math.unipd.it/~frossi/2010.1-er.pdf
Dunque ricontrollando, ho scoperto che la tua sintassi è corretta, e pure la mia
Uso normalmente le regex in cui le parentesi [] sono il raggruppamento.@BHK
Per costruire le espressioni regolari si può usare un semplice algoritmo che trasforma il tuo automa (sotto forma di grafo disegnato come normalmente lo conosci, che è la cosa più intuitiva) nel grafo di espressione che contiene gli archi etichettati con espressioni regolari, che poi semplifichi con la tecnica di eliminazione degli stati.
Informalmente, pensa al cammino dallo stato iniziale del tuo automa verso il suo stato finale:
- sostituisci il simbolo '1' dell'arco da q1 in sé stesso (laccio) con l'espressione 1*
- togli il laccio
- aggiungi l'espressione trovata al successivo arco del cammino verso lo stato finale, ottenendo un arco con l'espressione '1*0'
- sostituisci i simboli '1' e '0' del laccio di q2 con l'espressione '(0|1)*' e togli il laccio
- aggiungi l'espressione all'unico arco dallo stato iniziale allo stato finale, ottenendo '1*0(0|1)*'
Se hai un automa con più stati finali e/o più cammini, le operazioni devono essere fatte per ogni cammino verso ogni stato finale.
Datti un'occhiata a queste slide che ti illustrano il procedimento, c'è anche un esempio:
http://www.math.unipd.it/~frossi/2010.1-er.pdf
"Rggb":
Cosa vuoi dire con "si indica anche con +"?
Che l'espressione avrebbe potuto anche essere scritta:
1*0(0+1)*
@Piz
Ho notato, alcuni usano questa notazione (vedi anche le slide da me segnalate), che effettivamente è valida. Solo che per me è "innaturale", ma del resto ho alcune idiosincrasie ineliminabili.
Ho notato, alcuni usano questa notazione (vedi anche le slide da me segnalate), che effettivamente è valida. Solo che per me è "innaturale", ma del resto ho alcune idiosincrasie ineliminabili.
Con un atoma:
Ho eliminato q3;
Sto seguendo un procedimento giusto?
Ho eliminato q3;
Sto seguendo un procedimento giusto?
"BHK":
Sto seguendo un procedimento giusto?
Mi pare proprio di sì!
"Rggb":
Ho notato, alcuni usano questa notazione (vedi anche le slide da me segnalate), che effettivamente è valida. Solo che per me è "innaturale", ma del resto ho alcune idiosincrasie ineliminabili.
Anch'io preferisco la barra verticale, ma se non sbaglio il + è usato pure dall'Hopcroft-Motwani-Ullman... Quindi dovevo specificarlo!
quindi acetta espressioni regolari in questa forma:
se $R_(x)$ sta per [0..9]
e $R_(y)$ sta per [0..3]
avremo ((0+1)+2) + { ( $R_(x)$:6) +($R_(y)$:6) +($R_(x)$:[0..5]$R_(x)$) + ($R_(y)$:[0..5]$R_(x)$)}
"BHK":
quindi acetta espressioni regolari in questa forma:
se $R_(x)$ sta per [0..9]
e $R_(y)$ sta per [0..3]
avremo ((0+1)+2) + { ( $R_(x)$:6) +($R_(y)$:6) +($R_(x)$:[0..5]$R_(x)$) + ($R_(y)$:[0..5]$R_(x)$)}
No, quel + in grassetto dovrebbe essere una concatenazione, altrimenti hai scritto che il tuo linguaggio accetta anche le parole "2", "0" o "1".
Inoltre se la parola inizia con "2" deve per forza finire con "[0..3]:6" o con "[0..3]:[0..5][0..9]".
Invece, se inizia per "(0+1)" deve per forza finire con "[0..9]:6" o con "[0..9]:[0..5][0..9]".
Quindi direi che l'espressione regolare associata è:
(0+1)([0..9]:6 + [0..9]:[0..5][0..9]) + 2([0..3]:6 + [0..3]:[0..5][0..9])
che ricorda molto il linguaggio accettato da un orologio digitale del tipo hh:mm, se non fosse per quel ":6" che non mi spiego cosa sia.
mm si ho capito.
il 6 ovviamente rappresenta 60 minuti.
il 6 ovviamente rappresenta 60 minuti.
Probabile, ma è un numero che non compare sul display. Forse serve nell'implementazione, nel codice vero e proprio. 
L'automa l'ho creato io per fare pratica, ovviamente accetta una stringa come 21:6 (uguale a 22:00) dove dopo il sei c'è per forza di cose uno 0, che ho preferito non mettere come etichetta.
associate gli automi alle seguenti espressioni regolari:
provo a procedere per parti.
prima faccio l'automa che riconosce 0(0*+1)1*
poi (0*+0*1)
ci dovrebbe essere ε sul primo arco.
poi (1*+0)
Ø*ε non so come rappresentarlo
provo a procedere per parti.
prima faccio l'automa che riconosce 0(0*+1)1*
poi (0*+0*1)
ci dovrebbe essere ε sul primo arco.poi (1*+0)
Ø*ε non so come rappresentarlo
"BHK":
associate gli automi alle seguenti espressioni regolari:
Provo a "tradurre" (il carattere '+' mi "disturba") con
0(0*|1)1*|(0*|0*1)(1*|0)
per ora lascio perdere l'espressione $O/ epsilon$.
"BHK":
prima faccio l'automa che riconosce 0(0*+1)1*
Ok, però è non-deterministico; se ti va bene...
"BHK":
poi (0*+0*1) ... ci dovrebbe essere ε sul primo arco.
Giusto, da p0 a p1.
"BHK":
poi (1*+0)
Questo non mi torna: magari volevi mettere un laccio con '1' su g2?
"BHK":
Ø*ε non so come rappresentarlo
Neanche io, a meno non sia (0*)... sicuro faccia parte dell'espressione? Dove l'hai trovato?
si nell'automa per (1*+0) manca l'arco da g2 in g2 con 1.
perchè dici che il primo non è deterministico?
perchè dici che il primo non è deterministico?
Non solo il primo. Lo dico perché stai usando l'algoritmo di Thompson, che crea un NFA (difatti hai $epsilon$-transizioni).
Hai poi trovato quel zero-barra-epsilon da dove viene?
Hai poi trovato quel zero-barra-epsilon da dove viene?
allora un automa è detto non deterministico quando con una stessa etichetta posso raggiungere, partendo da uno stato due stati diversi.
Inoltre non c'è differenza visto che un DFA è equivalente a un NFA e a un ε-NFA.
per quanto riguarda Ø non ho capito se vale come lo 0 nel prodotto, ovvero (0+1)Ø=Ø
Inoltre non c'è differenza visto che un DFA è equivalente a un NFA e a un ε-NFA.
per quanto riguarda Ø non ho capito se vale come lo 0 nel prodotto, ovvero (0+1)Ø=Ø
allora il linguaggio Ø* si rappresenta così:
lo stato iniziale è finale
lo stato iniziale è finale
Ovvero il linguaggio vuoto. Non ho capito perché l'hanno messo nella regex, ma tant'è...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo