[AUTOMA] Espressione Regolare assocciata a un DFA

[gabry451]

Ho creato questo DFA che contiene parole con un numero dispari di b e un numero pari di a e non contengono la stringa "ab".



Ho provato a trovare l' espressione regolare associata a questo DFA e ho trovato:

(bb)* + (bb)* a(aa)*

Mi potete dire se è corretta? Esiste un metodo meccanico per poterla calcolare?

[Rggb1]

Lo schema dell'automa mi torna, la RE meno... direi più semplicemente
b(bb)* (aa)*

PS. "assocciata"?

[gabry451]

Grazie hai ragione, ma sarebbe equivalente a questa espressione giusto?
b(bb)* + b(bb)* a(aa)*a

O mi sbaglio? Perchè devo tenere conto dei due stati finali

[Rggb1]

Il numero di 'b' nella stringa che corrisponde alla RE che hai messo è pari, e non dispari come richiesto.

Inoltre non capisco cosa intendi con "tenere conto dei due stati finali".

[gabry451]

"Rggb":Il numero di 'b' nella stringa che corrisponde alla RE che hai messo è pari, e non dispari come richiesto.

Inoltre non capisco cosa intendi con "tenere conto dei due stati finali".

Scusa dove lo vedi che è pari?

b(bb)* + (bb)*b a(aa)*a

Per i due stati finali abbiamo sia q1 che è uno stato finale sia q3.

Per arrivare a q1 la RE è:

b(bb)*

Per arrivare a q3 la RE è:
b(bb)*a(aa)*a

Per cui la RE associata all' automa è:
b(bb)* + (bb)*b a(aa)*a

In parole povere possiamo accettare o b(bb)* oppure (bb)*b a(aa)*a.

L' espressione b(bb)* + (bb)*b a(aa)*a dovrebbe equivalere a quella che hai postato per il semplice motivo che la star di Klenee può assumere anche una concatenazione di 0 elementi per cui potrei avere:

b(bb)* + b(bb)* a(aa)*a = b(bb)* (aa)*

Che è esattamente l' espressione regolare che hai postato. Sbaglio qualcosa?

[Rggb1]

Va bene, usi la notazione '+' per or esclusivo, cosa che normalmente io non uso poiché '+' rappresenta "uno o più", in sua vece metto '|', ma basta capirsi.

Tutto corretto.