[ALGORITMO] Automa a stati finiti

[Vincenzoflamini]

Salve cortesemente sapreste spiegarmi la procedura per svolgere il seguente esercizio?

Sia data la seguente specifica funzionale di una
macchina sequenziale sincrona con un ingresso x ed
un uscita z:
L'uscita al tempo t vale 1 se in ingresso si è
presentata la sequenza 010. Le sequenze possono
essere anche sovrapposte (es., se la sequenza di
ingresso è 00101010, la sequenza d'uscita sarà
00010101).
Tracciare il diagramma degli stati e ricavare la
tabella degli stati

Vorrei capire innanzitutto quali sono gli ingressi possibili e come identificarli e poi la sovrapposizione ... ho cercato un po in internet per trovare delle buone guide ma niente e a breve ho l'esame di architettura dei calcolatori!

[c_junior]

allora qualche giorno fa ho dato un esame su questa roba...dovrebbe essere più o meno cosi ma non ti assicuro niente

q0-se x=0 vai in q1 output 0
   -se x=1 vai in q0 output 0

q1-se x=1 vai in q2 output 0
   -se x=0 vai in q1 output 0

q2-se x=0 vai in q1 output 1
   -se x=1 vai in q0 output 0 

[YuYevon]

Corretto il ragionamento di c_junior.

La tabella degli stati è questa

    1     0
q0 q0/0 q1/0
q1 q2/0 q0/0
q2 q0/0 q1/1

Il fatto che la sequenza possa essere sovrapposta significa che, una volta ricevuto 010, lo stato della macchina non si resetta perché l'ultimo 0 ricevuto non solo completa la sequenza corretta ma potrebbe anche essere il primo 0 di una nuova sequenza, visto che questa inizia e finisce con 0. È per questo che dallo stato q2, con ingresso 1, la macchina si porta nello stato q1 e non q0 (quello iniziale): q1 infatti è proprio lo stato in cui è stato ricevuto il primo 0 della sequenza.

[Vincenzoflamini]

Ho provato a fare il diagramma degli stati, anche se volevo cerchiare lo stato Q1 xke ha output 1 xo mi sn chiesto ma lo stato Q1 potrebbe anke valere output 0 quindi come fare??
Tra l'altro quindi potrebbe fare un loop infinito qst programma non è un errore (se continuo a mettere 010 come sequenza)?

[YuYevon]

Originariamente inviato da Vincenzoflamini
Ho provato a fare il diagramma degli stati, anche se volevo cerchiare lo stato Q1 xke ha output 1 xo mi sn chiesto ma lo stato Q1 potrebbe anke valere output 0 quindi come fare??

Intendi dire che volevi cerchiare due volte lo stato q1 essendo quello finale? Credo si possa fare lo stesso, anche se conincide con uno stato intermedio. Comunque ti consiglio di specificare su ogni arco non solo l'ingresso, ma anche l'uscita corrispondente... ad esempio, sull'arco che da q0 ritorna in q0 scriverei 1/0, per dire "ingresso 1, uscita 0", stessa cosa per tutti gli altri archi.

Segnalo comunque che l'arco da q2 con ingresso 1 dovrebbe andare in q0, non ritornare in q2, inoltre nella tabella che ho scritto prima c'è un piccolo errore (anche se tu nel diagramma hai fatto bene): in q1, con ingresso 0 si può rimanere in q1, non necessariamente si deve tornare a q0, quindi

    1     0
q0 q0/0 q1/0
q1 q2/0 q1/0
q2 q0/0 q1/1

come tra l'altro aveva giustamente scritto c_junior.

Originariamente inviato da Vincenzoflamini
Tra l'altro quindi potrebbe fare un loop infinito qst programma non è un errore (se continuo a mettere 010 come sequenza)?

"infinito" è una parola grossa... continuerà fino a quando ci saranno degli ingressi :)

[Vincenzoflamini]

Originariamente inviato da YuYevon
Segnalo comunque che l'arco da q2 con ingresso 1 dovrebbe andare in q0, non ritornare in q2,

Infatti...ogni volta ke non si sta seguendo la sequenza di ingresso voluta si ritorna allo stato iniziale giusto?

Grazie mille delle risposte

[YuYevon]

Originariamente inviato da Vincenzoflamini
ogni volta ke non si sta seguendo la sequenza di ingresso voluta si ritorna allo stato iniziale giusto?

Solo se gli ultimi n bit ricevuti non possono essere inizio della sequenza corretta (almeno nel caso della possibilità di avere sequenze sovrapposte). Ad esempio, se ricevessi la sequenza 0010, il secondo 0 non sarebbe atteso eppure non ritorneresti allo stato iniziale perché quello 0 potrebbe essere il primo della sequenza corretta. Se invece avessi 0110 allora al terzo input (1) dovresti ritornare in q0 perché 011 non potrebbe in alcun modo essere l'inizio di una sequenza corretta, visto che questa è 010.

[Vincenzoflamini]

Originariamente inviato da YuYevon
Solo se gli ultimi n bit ricevuti non possono essere inizio della sequenza corretta (almeno nel caso della possibilità di avere sequenze sovrapposte). Ad esempio, se ricevessi la sequenza 0010, il secondo 0 non sarebbe atteso eppure non ritorneresti allo stato iniziale perché quello 0 potrebbe essere il primo della sequenza corretta. Se invece avessi 0110 allora al terzo input (1) dovresti ritornare in q0 perché 011 non potrebbe in alcun modo essere l'inizio di una sequenza corretta, visto che questa è 010.

quindi nel caso di sequenze sovrapposte visto ke l'ultimo bit ricevuto 0 anche se sono nello stato Q1 puo essere l'inizio della nuova sequenza allora rimane li, ma se invece si trattasse di sequenze NON sovrapposte si resetta allo stato iniziale? Aspetta quel tuo "ultimi N bit " mi confonde :
se io da Q0 passo a Q1 e poi a Q2 con la sequenza 010 e mettiamo caso ke la sequenza da accettare sia 0101 ...
allora nello stato Q2 se l'ingresso ho uno 0 ke nn va bene ritorno allo stato iniziale o su se stesso? aspettando ke arrivi un 1 visto ke "gli ultimi N bit " erano giusti

[YuYevon]

Originariamente inviato da Vincenzoflamini
quindi nel caso di sequenze sovrapposte visto ke l'ultimo bit ricevuto 0 anche se sono nello stato Q1 puo essere l'inizio della nuova sequenza allora rimane li, ma se invece si trattasse di sequenze NON sovrapposte si resetta allo stato iniziale?

Corretto. Per la precisione, rimani lì perché q1 è proprio lo stato in cui è stato riconosciuto il primo 0; se questo stato fosse un generico qx, torneresti in qx.

Originariamente inviato da Vincenzoflamini
Aspetta quel tuo "ultimi N bit " mi confonde :
se io da Q0 passo a Q1 e poi a Q2 con la sequenza 010 e mettiamo caso ke la sequenza da accettare sia 0101 ...
allora nello stato Q2 se l'ingresso ho uno 0 ke nn va bene ritorno allo stato iniziale o su se stesso? aspettando ke arrivi un 1 visto ke "gli ultimi N bit " erano giusti

Aspetta se la sequenza da accettare è 0101 e non 010 la situazione ovviamente cambia, avrai 4 stati e non 3. Comunque una volta ricevuta la sequenza 010, se ricevi 0 anziché 1 ti ritrovi con 0100. Ora analizzando 0100 si nota che l'ultimo 0 può essere l'inizio della sequenza corretta (che è 0101), quindi torni nello stato in cui è stato ricevuto appunto il primo 0 (supponiamo q1). Gli ultimi due bit invece (00) non coincidono con l'inizio della sequenza corretta, se la sequenza iniziasse con 00 si potrebbe tornare nello stato relativo, ma con questo esempio non è così. Ancora peggio per gli ultimi 3 (100) e gli ultimi (0100).

Piuttosto, una volta avuti i bit 010, se ricevi 1 non soltanto setti l'uscita a 1 (perché la sequenza è completa) ma ritorni addirittura nel secondo stato, quello in cui hai ricevuto 01, perché appunto gli ultimi due bit (01) possono essere i primi due di una nuova sequenza corretta.

[Vincenzoflamini]

Scusami il disturbo , sapresti dirmi come svolgere qst tipo do esercizio sugli automi non capisco che vuol dire al K-esimo oppure x(k-1) ecc..

Sia data la seguente specifica funzionale di una macchina a stati finiti sincrona con un ingresso (x)
ed una uscita (z).
Indicati con x(k) e z(k) rispettivamente l’ingresso e l'uscita della macchina al k-esimo ciclo di clock
si ha che:
z(k) = 1 se x(k)=!x(k-1), x(k-1)=!x(k-2) e x(k-2)=1, altrimenti z(k)=0.
1. Tracciare il diagramma degli stati.
2. Ricavare la tabella degli stati