Diagramma degli stati

[Shika93]

Può tornare indietro da C a B?
In B riconosce il primo 0; in C riconosce 1 e non dovrebbe andare ad un altro stato a parte per riconoscere l'ultimo 0?
Può stare su uno stato già utilizzato?

Chiedo perché nelle mie dispense c'è un esempio, riconoscere la sequenza e la fa così



Infatti da A a B riconosce il primo 1; da B a C riconosce il secondo 1; da C a D riconosce lo 0 e per riconoscere l'ultimo 1 torna a B perché si chiedeva di riconoscere la sequenza nella stringa dove questa sequenza appare due volte con un in comune (a metà)

Se fosse come nello schema che hai fatto tu, per riconoscere il secondo 1 potrebbe stare in B con

Potrei sbagliare, ma quando sono in D e ricevo uno '0' io sarei rimasto in D, non sarei tornato in A.

Sono d'accordo. Per tornare in A non dovrei avere ? D riconosce già 0

[c1b8]

per riconoscere l'ultimo 1 torna a B perché si chiedeva di riconoscere la sequenza nella stringa 1101101 dove questa sequenza appare due volte

No!
Non torna in B perché si chiede di riconoscere quella sequenza doppia, anche se la sequenza fosse stata 1101001001101 sarebbe dovuto tornare in B.

[DanteCpp]

Potrei sbagliare, ma quando sono in D e ricevo uno '0' io sarei rimasto in D, non sarei tornato in A.

Hai ragione, per riconoscere le sequenze del tipo 00010:

D = (D,0)
0 = (D,0)

Dove omega è la funzione delle uscite definita:



e l'alfabeto delle uscite.

[Shika93]

per riconoscere l'ultimo 1 torna a B perché si chiedeva di riconoscere la sequenza nella stringa 1101101 dove questa sequenza appare due volte

No!
Non torna in B perché si chiede di riconoscere quella sequenza doppia, anche se la sequenza fosse stata 1101001001101 sarebbe dovuto tornare in B.

perché? Non poteva tornare in A allora? Una volta conclusa la sequenza, ricomincio da capo per un'altra scansione...

[DanteCpp]

Cosi facendo non riesci a riconoscere le parole sovrapposte, ma solo quelle concatenate...

[Shika93]

Quindi è come ho detto sopra, no? Per riconoscere l'1 in mezzo e avere due sequenze riconosciute anzichè solo la prima o solo l'ultima...

[DanteCpp]

L'automa che ho proposto riconosce alla perfezione l'input d'esempio, poi con la correzione di c1b8 riconosce anche le parole del tipo 00010. Non capisco cosa non ti convinca, comunque per non buttare parole al vento potresti disegnare il graffo, cosi c'intendiamo!

[Shika93]

Pensavo di averlo già messo. Io l'avevo pensato così.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

[DanteCpp]

Inanzi tutto, il tuo automa è non deterministico, ossia partendo da uno stato è possibile finire in due stati diversi con una transazione etichettata allo stesso modo.

Formalmente:

tale che



con

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Naturalmente non ha senso implementare una macchina non deterministica, dal momento che non possiamo definirne il comportamento, ma sin qui poco male, dal momento che ogni automa non deterministico(NFA) può essere convertito in un automa deterministico(DFA).

Il problema è che il tuo automa non riconosce neanche, l'input d'esempio come dovrebbe...

Proviamo a eseguire una computazione con il tuo automa, partiamo dallo stato A e leggiamo il primo simbolo di I. Man mano che leggiamo I lo consumiamo e riempiamo U:

I = 1101100100110100
U =



I = 101100100110100
U = 0



I = 01100100110100
U = 00



I = 1100100110100
U = 000



Qui entra in gioco il non determinismo, ma noi conosciamo il comportamento che deve avere quindi prendiamo il ramo giusto, scegliendo:


I = 100100110100
U = 0000



I = 00100110100
U = 00000



I = 0100110100
U = 000000



I = 100110100
U = 0000000



I = 00110100
U = 00000001



I = 0110100
U = 000000010

Come vedi già a questo punto, l'automa non rispetta l'output d'esempio!

[Shika93]

Quindi io devo vedere su I cosa vedo.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Mi sa di minchiata...Io l'ho pensata così come hai fatto tu.
il primo bit di I è 1, nessuna sequenza che devo riconoscere parte da 1, quindi resto in A;
il secondo bit è un altro 1. Idem. Resto in A;
il terzo bit è uno 0, ok. Vado in B;
il quarto bit è un 1, ok potrebbe essere la seconda sequenza. Vado in C;
il quinto bit è un 1; niente. Resto in C;
il sesto è uno 0, ok vado in D;
e così via...

Se è sbagliato a questo punto non so che fare.