Conversione automa da Non Deterministico a Deterministico

[krak2]

Costruire un automa a stati finiti deterministico equivalente al seguente automa non deterministico

	a	b
{q1,q2}	{q2}	q2
{q1}	q3	{q2}

q1=stato iniziale
q2= stato finale.

Ecco l'automa deterministico che ho ricavato:
http://i976.photobucket.com/albums/ae241/mokkono/automa_zpsc7077586.jpg
E' corretto?

[onlyReferee]

Ciao krak!
Premetto che non capisco perché non riesco a vedere l'immagine presente al link che hai postato (utilizzo Chrome ma non credo sia questo il problema): il browser va avanti a caricarla senza visualizzarla (ho atteso cinque minuti circa).
In ogni caso il mio primo suggerimento è cercare di capire qual è il linguaggio che l'automa prova a riconoscere (anche se credo tu lo abbia già fatto forse).
Io mi sono fatto la mia idea, volevo appunto confrontarla con la tua .

[krak2]

Ciao,
sinceramente non so perchè non riesce a caricare l'immagine, a me la apre senza problemi.
Ad ogni modo, ti riporto il diagramma di transizione dell'automa che avevo disegnato in quell'immagine in modo da poter confrontare la soluzione.

	a	b
{q1,q2}	q2	q2
\(\displaystyle \phi \)	{q1,q2}	{q1,q2,q3}
{q1,q2,q3}	{q1,q2,q3}	{q1,q2}

con:
q1=stato iniziale
{q2}, {q1,q2}, {q1,q2,q3}= stati finali.

E' corretto?
Grazie

[onlyReferee]

Ciao krak,
scusa per il lieve ritardo della risposta innanzitutto. Ho provato a convertire l'automa richiesto (ho ricontrollato una seconda volta per sicurezza) in uno deterministico. Non mi torna però quello di cui hai riportato la funzione di transizione nella tabellina: noto in particolare che ti manca lo stato corrispondente a $\{q_2, q_3\}$ e che non hai transizioni a partire da $q_2$. E' proprio questa seconda nota che dovrebbe farti venire il dubbio: se uno degli stati del nuovo automa non ha transizioni che ragione potrebbe avere di esistere? Nessuna! Pertanto è probabile che tu abbia sbagliato qualcosa nello scrivere la nuova funzione di transizione.
Nel nuovo automa puoi avere fino a $2^n - 1$ stati, dove $n$ è il numero degli stati dell'automa originale. Prova a correggere e fammi sapere se non ti trovi, sarò felice di aiutarti nuovamente in tal caso .

[krak2]

Ciao onlyReferee,
grazie alla tua risposta ho ricontrollato l'automa. In effetti non sono molto pratico ancora con questi esercizi e quello che mi serve è un pò di aiuto nel capire dove sbaglio.

L'ho rifatto, ecco il nuovo automa:

	a	b
{q1,q2}	q2	q2
q1	{q1,q2}	{q1,q2,q3}
{q2,q3}	{q2,q3}	{q1,q2}
{q1,q2,q3}	{q1,q2}

con:
{q1} = stato iniziale.
{q2}, {q1,q2}, {q2,q3}, {q1,q2,q3} = stati finali

Corretto?
Sempre grazie dell'aiuto.

[onlyReferee]

Perfetto, ora tutto torna Per motivi di praticità e chiarezza si tende inoltre ad assegnare un nome ai nuovi stati (ad esempio nel nostro caso possiamo avere $\{q_1\} = k_1, \{q_2\} = k_2, \{q_1, q_2\} = k_3, \cdots, \{q_1, q_2, q_3\} = k_7$) ma è solo una questione di convenzione, nulla più.

[krak2]

Innanzitutto ti ringrazio dell'aiuto che mi stai dando.
A mò di esercitazione ho svolto anche quest'altro esercizio, correggimi se ho sbagliato qualcosa.

Costruire un automa a stati finiti deterministico equivalente al seguente automa non deterministico

	a	b	c
{q1,q2}	q2	{q1,q3}	q2
{q2,q3}	q1	q3	{q1,q3}
{q1,q2}

con
q1 = stato iniziale
q3 = stato finale.

Ecco l'automa deterministico che ho ricavato:

	a	b	c
{q1,q2}	q2	{q1,q3}	q2
{q2,q3}	q1	{q1,q2}	{q1,q2}
{q1,q3}	{q1,q3}	{q1,q2,q3}	{q2,q3}
{q2,q3}	{q1,q2,q3}	{q2,q3}	{q1,q2}
{q1,q2,q3}	{q2,q3}	{q1,q2,q3}

con
q1 = stato iniziale
{q1,q3}, {q2,q3}, {q1,q2,q3} = stati finali.

E' corretto? Sempre grazie dell'aiuto onlyReferee

[onlyReferee]

Perfetto, ho appena riprovato a farlo per conto mio e mi torna . Ormai dopo qualche esercizio mi sembra che il procedimento generale ti sia chiaro . Felice di aiutarti.

[krak2]

Ciao onlyReferee,
in effetti adesso è tutto più chiaro.
Ti ringrazio tantissimo per l'aiuto che mi hai dato.