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 è
La tabella di transizione per Moore Machine è:
serpente pitone contro anaconda
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à,
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:
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à:
Ora inseriremo le possibilità di 0 e 1 per ogni stato. Pertanto la macchina di Moore diventa:
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à:
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à: