logo

Macchina Moore

La macchina di Moore è una macchina a stati finiti in cui lo stato successivo è deciso dallo stato corrente e dal simbolo di input corrente. Il simbolo di uscita in un dato momento dipende solo dallo stato attuale della macchina. La macchina di Moore può essere descritta da 6 tuple (Q, q0, ∑, O, δ, λ) dove,

 Q: finite set of states q0: initial state of machine ∑: finite set of input symbols O: output alphabet δ: transition function where Q × ∑ → Q λ: output function where Q → O 

Esempio 1:

Il diagramma di stato per Moore Machine è

Macchina Moore

La tabella di transizione per Moore Machine è:

serpente pitone contro anaconda
Macchina Moore

Nella macchina di Moore sopra, l'output è rappresentato con ciascuno stato di input separato da /. La lunghezza di output per una macchina di Moore è maggiore di quella di input di 1.

Ingresso: 010

Transizione: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2

Produzione: 1110(1 per q0, 1 per q1, ancora 1 per q1, 0 per q2)

Esempio 2:

Progetta una macchina di Moore per generare il complemento a 1 di un dato numero binario.

Soluzione: Per generare il complemento a 1 di un dato numero binario la logica semplice è che se l'input è 0 l'output sarà 1 e se l'input è 1 l'output sarà 0. Ciò significa che ci sono tre stati. Uno stato è lo stato iniziale. Il secondo stato consiste nel prendere gli 0 come input e produrre l'output come 1. Il terzo stato consiste nel prendere gli 1 come input e produrre l'output come 0.

Quindi la macchina di Moore sarà,

Macchina Moore

Ad esempio, prendi quindi un numero binario 1011

Ingresso 1 0 1 1
Stato q0 q2 q1 q2 q2
Produzione 0 0 1 0 0

Quindi otteniamo 00100 come complemento a 1 di 1011, possiamo trascurare lo 0 iniziale e l'output che otteniamo è 0100 che è il complemento a 1 di 1011. La tabella delle transazioni è la seguente:

Macchina Moore

Quindi la macchina di Moore M = (Q, q0, ∑, O, δ, λ); dove Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. la tabella di transizione mostra le funzioni δ e λ.

Esempio 3:

Progetta una macchina di Moore per una sequenza di input binaria tale che se ha una sottostringa 101, la macchina produce A, se l'input ha una sottostringa 110, restituisce B altrimenti restituisce C.

Soluzione: Per progettare una macchina del genere, controlleremo due condizioni, e quelle sono 101 e 110. Se otteniamo 101, l'output sarà A, e se riconosciamo 110, l'output sarà B. Per le altre stringhe, l'output sarà C.

caso interruttore java

Il diagramma parziale sarà:

Macchina Moore

Ora inseriremo le possibilità di 0 e 1 per ogni stato. Pertanto la macchina di Moore diventa:

Macchina Moore

Esempio 4:

Costruisci una macchina di Moore che determina se una stringa di input contiene un numero pari o dispari di 1. La macchina dovrebbe fornire 1 come output se nella stringa è presente un numero pari di 1 e 0 altrimenti.

Soluzione:

La macchina di Moore sarà:

Macchina Moore

Questa è la macchina Moore richiesta. In questa macchina, lo stato q1 accetta un numero dispari di 1 e lo stato q0 accetta un numero pari di 1. Non esiste alcuna restrizione sul numero di zeri. Pertanto, per l'ingresso 0, è possibile applicare il ciclo automatico su entrambi gli stati.

elenco Java nell'array

Esempio 5:

Progetta una macchina di Moore con l'alfabeto di input {0, 1} e l'alfabeto di output {Y, N} che produce Y come output se la sequenza di input contiene 1010 come sottostringa altrimenti produce N come output.

Soluzione:

La macchina di Moore sarà:

Macchina Moore