Costruire l'automa relativo all'espressione regolare

[krak2]

Costruire un automa a stati finiti denotato dalla seguente espressione regolare:
[(ac)* bbbca (cb)* ab]* U [(bbcc)* (b U a)* abca (ca)*]*

Questo è l'automa che ho ricavato:
http://imageshack.us/photo/my-images/14/8ri9.jpg/
E' corretto?
(la "e" sta per la \(\displaystyle \varepsilon \) di stringa vuota)
Grazie.

[onlyReferee]

La parte sopra è quasi perfetta. Qui ti manca solo uno stato in più tra 6 e 7 a cui arrivi tramite una $b$. Da questo nuovo stato puoi transitare regolarmente al 7 tramite una $c$. Inoltre lo stato 12 non ti serve: da 11 con una $b$ torni direttamente ad 1, stato di accettazione.
La parte sotto purtroppo ancora non va bene. Da 2 a 13 ci vai direttamente con una $b$, non ha senso replicare l'epsilon mossa. Di conseguenza da 14 a 15 ti serve una $c$ e non una $b$ per procedere. Anche l'etichetta da 16 a 13 va cambiata (da $c$ a $b$ precisamente). La transizione
da 18 a sé stesso tramite $a, b$ non va fatta qui ma in 17. Da 17 a 18 basta una epsilon-mossa. 24 non ti serve: da 23 puoi tornare indietro a 22 con $a$. Infine da 23 torni a 2 con una semplice epsilon-mossa. Fiuuu ...

[krak2]

Ciao onlyReferee,
non ho ben capito questo passaggio:

"onlyReferee": 24 non ti serve: da 23 puoi tornare indietro a 22 con $ a $.

nel senso che, eliminando lo stato 24, la rappresentazione di \(\displaystyle (ca)* \) viene così?:
http://imageshack.us/photo/my-images/826/ps1g.jpg/

Inoltre ho aggiunto la e-transizione perchè in teoria \(\displaystyle (ca)* \) può essere anche vuota.

Ti faccio vedere tutta la parte inferiore, così capisci meglio:
http://imageshack.us/photo/my-images/834/b727.jpg/

Lo so che è stata una faticaccia per te, ma mi stai aiutando molto. Grazie

[onlyReferee]

"krak":Ciao onlyReferee,
non ho ben capito questo passaggio:
[quote="onlyReferee"] 24 non ti serve: da 23 puoi tornare indietro a 22 con $ a $.

nel senso che, eliminando lo stato 24, la rappresentazione di \(\displaystyle (ca)* \) viene così?:
http://imageshack.us/photo/my-images/826/ps1g.jpg/
[/quote]
No, nel senso che, nell'ultima immagine che hai postato, 22 e 23 non devono essere collegati tra loro. Da 22 puoi tornare a 21 con una $a$ (arrivarci da 21 con $c$ è corretto così com'è adesso). Di conseguenza nemmeno 23 ti serve più dopo questa sistemazione poiché ti basta far partire una epsilon-mossa da 21 a 2 per poter consentire l'accettazione/ripetere il ciclo.

"krak":
Inoltre ho aggiunto la e-transizione perchè in teoria \(\displaystyle (ca)* \) può essere anche vuota.
Ti faccio vedere tutta la parte inferiore, così capisci meglio:
http://imageshack.us/photo/my-images/834/b727.jpg/

Certo, come detto al punto precedente serve una epsilon-mossa...però bisogna cercare di usarne quante meno possibile e ridurre così gli stati in un'ottica di semplificazione .

"krak":
Lo so che è stata una faticaccia per te, ma mi stai aiutando molto. Grazie

Di nulla, il "fiuuu" del messaggio precedente l'ho scritto solo per sdrammatizzare un attimo .
PS: per la parte sopra è tutto chiaro, ti torna il discorso dopo le modifiche suggerite?

[krak2]

Ciao onlyReferee,
si adesso ho capito e per la parte finale è tutto chiaro
Riprendendo l'immagine di prima, la rappresentazione dagli stati 2 a 17 è corretta?
http://imageshack.us/photo/my-images/834/b727.jpg/
Grazie.

[onlyReferee]

Il collegamento da 16 a sé stesso tramite $a,b $ non va qui ma in 17 (da 16 parte solo la epsilon-mossa che hai messo ed è già corretta). Da 2 a 16 non parte alcuna freccia per 16: ne parte una per 17 mediante epsilon-mossa.
Rivedi bene 21, 22 e 23 in base a quello che ho scritto prima, non li hai sistemati correttamente... 23 non ti serve più!

[krak2]

Ciao onlyReferee,
non avevo ancora sistemato la parte finale poichè volevo che mi dicessi se era rappresentata correttamente la parte iniziale.
Comunque adesso ho sistemato tutto e l'automa finale dovrebbe essere questo:
http://imageshack.us/photo/my-images/89/043m.jpg/

Grazie della disponibilità e aiuto come sempre

[onlyReferee]

Ok, quasi perfetto. Unica nota (forse mi era sfuggita questa correzione): ti serve un altro stato da 17 a 18 a cui arrivi (da 17) con una epsilon-mossa. Da questo nuovo stato procedi poi tramite $a$ per 18. Non è che sia sbagliata la versione attuale però in 17 con a puoi fare due percorsi diversi con $a$ e questo rende l'automa non deterministico.
In teoria quando ha un'espressione regolare ti basta usare solo le epsilon-mosse senza ricorrere al non determinismo.

[krak2]

Ciao onlyReferee,
scusami se ti rispondo adesso, ma ieri non ho potuto.
Ho riscritto tutto l'automa inserendo anche quello stato con la e-mossa.

Ecco l'espressione regolare iniziale:
[(ac)* bbbca (cb)* ab]* U [(bbcc)* (b U a)* abca (ca)*]*

ed ecco l'automa completo:
http://imageshack.us/photo/my-images/809/40s4.jpg/

Non finirò mai di ringraziarti per il proficuo aiuto e disponibilità che hai avuto nei miei confronti.
Grazie.

[onlyReferee]

Ciao krak!
Di nulla, figurati, è stato un piacere aiutarti per me. Ora l'automa è perfetto comunque . Sicuramente avrai capito bene gli errori commessi in precedenza nel costruire l'automa.
Consiglio: in generale ma soprattutto quando hai degli automi abbastanza complessi scomponi sempre il linguaggio nelle varie sottoespressioni che questo deve riconoscere e prova a descrivere un piccolo automa per ciascuna di esse.
Poi, una volta terminato, metti assieme tutto .
A presto!

[krak2]

Si certo adesso è tutto più chiaro.
Grazie del consiglio.
A presto onlyReferee