Aiuto con espressione regolare

[smartmouse]

Definire un'espressione regolare che denoti il linguaggio
L = {w ∈ {a, b}* | w ha un numero pari di occorrenze della lettera b}

Io sono arrivato a diverse conclusioni, l'ultima delle quali è questa (a* U (ba*b)*)*.
Ho provato anche ad disegnare il relativo automa

[img]https://scontent-mxp1-1.xx.fbcdn.net/hphotos-xfa1/v/t1.0-9/1497472_841666689255319_8675073401519682443_n.jpg?oh=870e1f667df6fd4d4f9d066140864e13&oe=56300EB4[/img]

dal quale poi ho cercato di utilizzare l'algoritmo per passare da un DFA (automa finito deterministico) ad un'espressione regolare, che mi ha portato alla seguente espressione: a*ba*b.

Voi come fareste questo esercizio?

[Cronovirus]

L'approccio di disegnare l'automa e poi applicare il teorema che ti permette di arrivare all'espressione regolare direi che è l'approccio migliore. L'automa mi sembra corretto quindi se hai applicato bene l'algoritmo direi che è tutto ok

[onlyReferee]

Ciao smartmouse
L'automa mi sembra corretto così come anche la prima espressione regolare che hai scritto. A questo punto forse però c'è stato qualche errore nel passaggio dal DFA all'espressione regolare dato che la seconda che hai scritto non è corretta.

[smartmouse]

Il problema è che non so se applico bene l'algoritmo!

Ho prima trasformato il DFA in NFA aggiungendo le epsilon transition:



Poi in 2 passaggi sono arrivato all'automa finale che mi ha fornito l'espressione regolare che dicevo prima:



Sbaglio qualcosa?

[apatriarca]

No.. I passaggi non sono corretti. Prima di tutto la stringa vuota è assolutamente valida. Valida è ancora la stringa in cui percorri solo a* e poi termini. Valida infine è anche la stringa in cui passi più volte per il percorso che hai osservato nella tua espressione regolare. L'espressione regolare corretta per quell'automa è insomma più o meno quella che avevi scritto all'inizio. Cioè \( (a^*(ba^*b)^*)^* \).

[smartmouse]

Grazie a questo sito sono giunto alla conclusione che la soluzione è la seguente:

\((a^*ba^*ba^*)^* \cup a^*\)

Ma sapresti indicarmi i passaggi corretti per disegnare il relativo NFA che conduce a tale soluzione?

[apatriarca]

L'automa era corretto.. Sono i passaggi che hai fatto per arrivare all'espressione regolare che non lo erano. Era in particolare sbagliato scrivere che dopo \(ba^*b\) dovessi necessariamente arrivare allo stato finale. Nell'automa che avevi scritto non era assolutamente corretto.

[apatriarca]

Nota che la tua soluzione può essere ancora semplificata. Puoi infatti osservare che date espressioni regolari \(A\) e \(B\), puoi riscrivere qualcosa nella forma \( (A^*\,B\,A^*)^* \cup A^* \) come \( A^* (B\,A^*)^* \).

[smartmouse]

"apatriarca":Nota che la tua soluzione può essere ancora semplificata. Puoi infatti osservare che date espressioni regolari \(A\) e \(B\), puoi riscrivere qualcosa nella forma \( (A^*\,B\,A^*)^* \cup A^* \) come \( A^* (B\,A^*)^* \).

EDIT: eh no, in questo caso vengono accettate anche stringhe con un numero dispari di b.

"apatriarca":L'automa era corretto.. Sono i passaggi che hai fatto per arrivare all'espressione regolare che non lo erano. Era in particolare sbagliato scrivere che dopo \(ba^*b\) dovessi necessariamente arrivare allo stato finale. Nell'automa che avevi scritto non era assolutamente corretto.

Ehm... potrei avere un disegnino?

[smartmouse]

Risolto tramite l'algoritmo spiegato abbastanza bene in questo video: https://www.youtube.com/watch?v=dBwx2PVicTY
La soluzione finale è questa: (a* U ba*b)*.

Grazie comunque a tutti per le vostre risposte.