Dubbio su automa a stati finiti

[Roran]

Devo progettare un automa che riconosca tre stringhe anche sovrapposte,le stringhe sono queste: 1100 - 1111 - 0011

ho un dubbio per quanto riguarda la sovrapposizione,mettiamo caso che mi trovi nello stato S1 (che ha già riconosciuto uno 0,dato che dallo stato iniziale S0 andrei allo stato S1 con uscita 0),nel caso ora inserissi un 1 mi troverei una sequenza 10 che ovviamente non compare in nessuna delle tre che devo riconoscere,devo tornare allo stato iniziale?oppure visto che il valore 1 che ho inserito può essere l'inizio di una di due sequenze,devo passare ad uno stato S2 che riconosce una sequenza composta da un solo valore cioè 1? Vi faccio un esempio più pratico qui sotto con i primi stati dell'automa:


Primo caso (ho usato | per separare le colonne della tabella,ho indicato gli stati con Sn e l'ipotetica sequenza,ovviamente all'interno della tabella i valori sono ordinati in "stato successivo/uscita"):

_____| 1 | 0
------------------
S0 - | 1/0 | 0/0
S1 0 | -/0 | 00/0
S2 1 |11/0 | -/0

Secondo caso:

_____| 1 | 0
------------------
S0 - | 1/0 | 0/0
S1 0 | 1/0 | 00/0
S2 1 |11/0 | 0/0

la differenza potete notarla guardando S1 con ingresso 1 e S2 con ingresso 0,quale dei due casi è quello corretto?

[clockover]

Non ho capito cosa vuol dire sovrapposte, ma penso comunque di aver capito quello che intendi.. Secondo me ti conviene prima di tutto costruirti un automa non deterministico e poi costruirti l'equivalente deterministico (a meno che quello non deterministico non ti vada già bene)... poi posso anche aver mancato qualcosa è da un po che non faccio sta roba :)

[Roran]

Non ho capito cosa vuol dire sovrapposte, ma penso comunque di aver capito quello che intendi.. Secondo me ti conviene prima di tutto costruirti un automa non deterministico e poi costruirti l'equivalente deterministico (a meno che quello non deterministico non ti vada già bene)... poi posso anche aver mancato qualcosa è da un po che non faccio sta roba :)per sovrapposte dovrebbe essere quando l'ultimo ingresso indipendentemente se la sequenza è stata completata o non risulta,può essere l'inizio di una nuova sequenza,ti faccio due esempi:

sequenza: 1100
l'ultimo 1 inserito indica che una delle tre sequenze è stata completata però potrebbe anche essere l'inizio di un'altra delle tre sequenze,per esempio in 0011100 si possono riconoscere le sequenze 0011 e 1100

sequenza: 10
l'ultimo 1 inserito non completa nessuna sequenza però potrebbe essere l'inizio di un altra

[demos88]

magari potrebbe aiutarti fare il diagramma a stati, una volta che hai quello, basta tradurlo, un procedimento abbastanza meccanico.

[Roran]

magari potrebbe aiutarti fare il diagramma a stati, una volta che hai quello, basta tradurlo, un procedimento abbastanza meccanico. mica tanto,cambia solo che è disegnato con gli archi,però il problema rimane,gli archi devono tornare allo stato iniziale oppure andare in uno stato tra 0 e 1 con uscita 0?

[clockover]

mica tanto,cambia solo che è disegnato con gli archi,però il problema rimane,gli archi devono tornare allo stato iniziale oppure andare in uno stato tra 0 e 1 con uscita 0?

Per questo ti ho detto di fare un automa non deterministico... guarda che il problema è più semplice di quello che pensi.

[Roran]

Per questo ti ho detto di fare un automa non deterministico... guarda che il problema è più semplice di quello che pensi.non fanno parte del programma del mio corso,ho visto ora su wikipedia cosa intendi,siamo partiti direttamente da mealy e moore + tabelle

[demos88]

mica tanto,cambia solo che è disegnato con gli archi,però il problema rimane,gli archi devono tornare allo stato iniziale oppure andare in uno stato tra 0 e 1 con uscita 0?
In realtà sono molto utili per avere una idea del problema se non sono troppo complicati. Comunque non capisco se non ti è chiaro il problema a livello di comprensione o risoluzione.
Non c'è nulla di particolarmente difficile, è ovvio che se ti dice che devi riconoscere le sequenze sovrapposte allora devi prevedere che se hai per esempio ricevuto 111 , sai che se ricevi un altro 1 riconosci la sequenza 1111 (e se poi ricevi 2 zeri di fila, riconosci pure 1100), mentre se ricevi zero, devi prevedere la possibilità che con un ulteriore 0 riconosci la sequenza 1100...
In 3 minuti ho buttato giù un diagramma a stati di una macchina di moore che risolve il problema, convertirla in tabella poi è banale...
Pensa a cose semplici, non complicarti la vita :)

[Roran]

In realtà sono molto utili per avere una idea del problema se non sono troppo complicati. Comunque non capisco se non ti è chiaro il problema a livello di comprensione o risoluzione.
Non c'è nulla di particolarmente difficile, è ovvio che se ti dice che devi riconoscere le sequenze sovrapposte allora devi prevedere che se hai per esempio ricevuto 111 , sai che se ricevi un altro 1 riconosci la sequenza 1111 (e se poi ricevi 2 zeri di fila, riconosci pure 1100), mentre se ricevi zero, devi prevedere la possibilità che con un ulteriore 0 riconosci la sequenza 1100...
In 3 minuti ho buttato giù un diagramma a stati di una macchina di moore che risolve il problema, convertirla in tabella poi è banale...
Pensa a cose semplici, non complicarti la vita :) non sono d'accordo sul fatto che se la macchina riceve due 0 di fila riconosce anche la sequenza 1100,questo perchè dopo i due 0 potrebbe essere inserito un altro 0 o 01 e quindi non completerei comunque un'altra sequenza,anche perchè la sequenza viene letta dal bit meno significativo verso quello più significativo.Comunque a parte questa cosa,diciamo che allora il caso giusto è il secondo? nel mio caso l'automa non torna mai allo stato iniziale perchè comunque una delle 3 sequenze inizia con 0,se iniziavano tutte con 1 allora dal momento che si presentava uno 0 dovevo tornare allo stato iniziale,dico bene?

[demos88]

non sono d'accordo sul fatto che se la macchina riceve due 0 di fila riconosce anche la sequenza 1100,questo perchè dopo i due 0 potrebbe essere inserito un altro 0 o 01 e quindi non completerei comunque un'altra sequenza,

Eh? :mbe:
Ipotizza di essere nella condizione che hai ricevuto 3 "1" di fila:
- ricevi un altro 1 -> 1111 riconosci la stringa "1111"
- ricevi uno "0" -> 1110, non riconosci niente.
Se hai ricevuto uno zero sopra e ne ricevi un altro, ottieni 11100, riconosci "1100"
Non capisco cosa ci sia di strano, e tanto per farla completa, se dopo 11100 ricevi 2 "1" vai a 1110011, e riconosci anche 0011. QUesto significa riconoscere le stringhe sovrapposte.

anche perchè la sequenza viene letta dal bit meno significativo verso quello più significativo.
A livello logico non cambia nulla, anche perchè delle stringhe da riconoscere, una è simmetrica (1111) e le altre due sono una l'inversa dell'altra, quindi in qualsiasi modo le ricevi, l'uscita è alta nelle stesse situazioni.
Che poi "leggere dal meno significativo al più significativo" cosa intendi dire? che se ricevo in ordine 0011, allora devo riconoscere 1100? Non cambia assolutamente nulla, proprio perchè se ricevo 1100 riconosco 0011 e l'uscita è comunque alta (sto supponendo che l'uscita sia alta quando riconosce una sequenza).
Se proprio volessi distinguere le stringhe, allora semplicemente implementa un automa che consideri questo fatto. Per esempio se dovessi riconoscere 1101 inserita rovescia, fai un automa che riconosca 1011 e sei a posto.

Comunque a parte questa cosa,diciamo che allora il caso giusto è il secondo? nel mio caso l'automa non torna mai allo stato iniziale perchè comunque una delle 3 sequenze inizia con 0,se iniziavano tutte con 1 allora dal momento che si presentava uno 0 dovevo tornare allo stato iniziale,dico bene?
Tipicamente lo stato iniziale in queste situazioni si ha solo all'inizio, poi non ci ritorna più.
Se ti fai un diagramma degli stati puoi verificarlo immediatamente...

[Roran]

Eh? :mbe:
Ipotizza di essere nella condizione che hai ricevuto 3 "1" di fila:
- ricevi un altro 1 -> 1111 riconosci la stringa "1111"
- ricevi uno "0" -> 1110, non riconosci niente.
Se hai ricevuto uno zero sopra e ne ricevi un altro, ottieni 11100, riconosci "1100"
Non capisco cosa ci sia di strano, e tanto per farla completa, se dopo 11100 ricevi 2 "1" vai a 1110011, e riconosci anche 0011. QUesto significa riconoscere le stringhe sovrapposte. c'è stato un equivoco,la lettura della sequenza nel mio caso deve essere fatta obbligatoriamente da destra verso sinistra,quindi la tua sequenza 11100 per me era intesa come 00111 :D

A livello logico non cambia nulla, anche perchè delle stringhe da riconoscere, una è simmetrica (1111) e le altre due sono una l'inversa dell'altra, quindi in qualsiasi modo le ricevi, l'uscita è alta nelle stesse situazioni.
Che poi "leggere dal meno significativo al più significativo" cosa intendi dire? che se ricevo in ordine 0011, allora devo riconoscere 1100? Non cambia assolutamente nulla, proprio perchè se ricevo 1100 riconosco 0011 e l'uscita è comunque alta (sto supponendo che l'uscita sia alta quando riconosce una sequenza).
Se proprio volessi distinguere le stringhe, allora semplicemente implementa un automa che consideri questo fatto. Per esempio se dovessi riconoscere 1101 inserita rovescia, fai un automa che riconosca 1011 e sei a posto.ti ho risposto nel punto sopra.

Tipicamente lo stato iniziale in queste situazioni si ha solo all'inizio, poi non ci ritorna più.
Se ti fai un diagramma degli stati puoi verificarlo immediatamente...ok mi basta questo per essere sicuro di procedere nel modo corretto,grazie.