Linguaggio generato da automa

[pino86]

Salve a tutti, avrei bisogno di confrontarmi con qualcuno di voi per un dubbio su come scrivere, mediante espressioni regolari, il linguaggio generato da un automa G, rappresentato dal seguente grafo:


Almeno una delle seguenti scritture è corretta?

a) L(G) = {a[(bba)*+(aca)*]*ac}* {ε+ a[(bba)*+(aca)*]* + a[(bba)*+(aca)*]*b + a[(bba)*+(aca)*]*bb + a[(bba)*+(aca)*]*a}

b) L(G) = [a(bba)*ac]* [ε + a(bba)* + a(bba)*b + a(bba)*bb + a(bba)*a]

Grazie anticipatamente a chiunque mi possa aiutare!

[Rggb1]

A naso, lo stato iniziale è $A$.

Ma lo stato finale qual è? Oppure tutti gli stati dell'automa sono stati finali?

[pino86]

Scusate mancano effettivamente delle informazioni.
Stato iniziale: A
Stato finale: C

[apatriarca]

La mia esperienza con queste cose è più pratica che teorica (e faccio riferimento forse ad una sintassi un po' diversa), ma scriverei l'espressione regolare nella forma: a(aca)*b(bab)*

[Rggb1]

@apatriarca
Manca qualcosa, infatti la stringa 'abbaacab' fa parte del linguaggio e non è esprimibile con la tua espressione. A me viene una espressione leggermente più articolata (ho controllato con JFlap e mi torna).
((aac)*ab(bab)*baac)*(aac)*ab(bab)*
Questa è la risoluzione di JFlap - manco a dirlo, con una sottoespressione (un "giro") in meno della mia fatta a mano

@pino86
Effettivamente l'uso che fai delle parentesi anche a me risulta un po' ostico. Comunque non mi sembra nessuna delle due espressioni sia corretta.

[apatriarca]

Hai ragione.. non avevo considerato la possibilità di tornare indietro dallo stato C ad A.

[pino86]

Si, è corretta quest'ultima espressione:
((aac)*ab(bab)*baac)*(aac)*ab(bab)*
Era tutto più semplice del previsto. Grazie ragazzi!