TechCodeview

Mooreův stroj je konečný stavový stroj, ve kterém o dalším stavu rozhoduje aktuální stav a aktuální vstupní symbol. Výstupní symbol v daném čase závisí pouze na aktuálním stavu stroje. Mooreův stroj lze popsat 6 n-ticemi (Q, q0, ∑, O, δ, λ), kde,

 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 

Příklad 1:

Stavový diagram pro Moore Machine je

Přechodová tabulka pro stroj Moore je:

arraylist a linkedlist

Ve výše uvedeném Mooreově stroji je výstup reprezentován každým stavem vstupu odděleným /. Výstupní délka pro Mooreův stroj je větší než vstupní o 1.

Vstup: 010

Přechod: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2

Výstup: 1110(1 pro q0, 1 pro q1, znovu 1 pro q1, 0 pro q2)

Příklad 2:

Navrhněte Mooreův stroj tak, aby generoval doplněk 1 daného binárního čísla.

Řešení: Pro generování doplňku 1 daného binárního čísla je jednoduchá logika taková, že pokud je vstup 0, pak výstup bude 1 a pokud je vstup 1, pak výstup bude 0. To znamená, že existují tři stavy. Jeden stav je počáteční stav. Druhý stav je pro přijímání 0 jako vstupu a vytváří výstup jako 1. Třetí stav je pro přijímání 1 jako vstupu a vytváření výstupu jako 0.

Mooreův stroj tedy bude,

Například vezměte jedno binární číslo 1011

Dostaneme tedy 00100 jako doplněk 1 1011, počáteční 0 můžeme zanedbat a výstup, který dostaneme, je 0100, což je doplněk 1 1011. Tabulka transakcí je následující:

Tedy Mooreův stroj M = (Q, q0, ∑, O, δ, λ); kde Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. přechodová tabulka ukazuje funkce δ a λ.

Příklad 3:

Navrhněte Mooreův stroj pro binární vstupní sekvenci tak, že pokud má podřetězec 101, výstup stroje A, pokud má vstup podřetězec 110, výstup B, jinak výstup C.

firma vs

Řešení: Pro návrh takového stroje zaškrtneme dvě podmínky, a to 101 a 110. Pokud dostaneme 101, výstup bude A, a pokud rozpoznáme 110, výstup bude B. Pro ostatní řetězce bude výstup C.

Částečný diagram bude:

Nyní vložíme možnosti 0 a 1 pro každý stav. Mooreův stroj se tak stává:

Příklad 4:

Sestrojte Mooreův stroj, který určí, zda vstupní řetězec obsahuje sudý nebo lichý počet jedniček. Stroj by měl dát jako výstup 1, pokud je v řetězci sudý počet jedniček a v opačném případě 0.

Řešení:

příkaz java switch

Stroj Moore bude:

Toto je požadovaný stroj Moore. V tomto stroji stav q1 přijímá lichý počet jedniček a stav q0 přijímá sudý počet jedniček. Počet nul není nijak omezen. Pro vstup 0 lze tedy použít vlastní smyčku na oba stavy.

Příklad 5:

Navrhněte Mooreův stroj se vstupní abecedou {0, 1} a výstupní abecedou {Y, N}, která produkuje Y jako výstup, pokud vstupní sekvence obsahuje 1010 jako podřetězec, jinak produkuje N jako výstup.

Řešení:

Stroj Moore bude: