logo

Mooreov stroj

Mooreov stroj je konečný stavový stroj, v ktorom o ďalšom stave rozhoduje aktuálny stav a aktuálny vstupný symbol. Výstupný symbol v danom čase závisí len od aktuálneho stavu stroja. Mooreov stroj možno opísať 6 n-ticami (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 

Príklad 1:

Stavový diagram pre Moore Machine je

Mooreov stroj

Prechodová tabuľka pre Moore Machine je:

získať aktuálny dátum v jave
Mooreov stroj

Vo vyššie uvedenom Mooreovom stroji je výstup reprezentovaný každým vstupným stavom oddeleným /. Výstupná dĺžka pre Mooreov stroj je väčšia ako vstup o 1.

Vstup: 010

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

Výkon: 1110(1 pre q0, 1 pre q1, opäť 1 pre q1, 0 pre q2)

Príklad 2:

Navrhnite Mooreov stroj na generovanie doplnku 1 daného binárneho čísla.

Riešenie: Na vygenerovanie doplnku 1 daného binárneho čísla je jednoduchá logika taká, že ak je vstup 0, potom výstup bude 1 a ak je vstup 1, potom výstup bude 0. To znamená, že existujú tri stavy. Jeden stav je počiatočný stav. Druhý stav je pre prevzatie 0 ako vstupu a produkciu výstupu ako 1. Tretí stav je pre prevzatie 1 ako vstupu a produkciu výstupu ako 0.

Preto bude Mooreov stroj,

Mooreov stroj

Napríklad vezmite jedno binárne číslo 1011

Vstup 1 0 1 1
Štát q0 q2 q1 q2 q2
Výkon 0 0 1 0 0

Takto dostaneme 00100 ako doplnok 1 k 1011, počiatočnú 0 môžeme zanedbať a výstup, ktorý dostaneme, je 0100, čo je doplnok 1 k 1011. Tabuľka transakcií je nasledovná:

Mooreov stroj

Teda Mooreov stroj M = (Q, q0, ∑, O, δ, λ); kde Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. prechodová tabuľka zobrazuje funkcie δ a λ.

stiahnite si video z youtube vlc

Príklad 3:

Navrhnite Mooreov stroj pre binárnu vstupnú sekvenciu tak, že ak má podreťazec 101, výstup stroja A, ak má vstup podreťazec 110, výstup B, inak výstup C.

Riešenie: Pre návrh takéhoto stroja skontrolujeme dve podmienky, a to 101 a 110. Ak dostaneme 101, výstup bude A a ak rozpoznáme 110, výstup bude B. Pre ostatné reťazce bude výstup C.

Čiastočný diagram bude:

Mooreov stroj

Teraz vložíme možnosti 0 a 1 pre každý stav. Mooreov stroj sa tak stáva:

pripojenia v jave
Mooreov stroj

Príklad 4:

Zostrojte Mooreov stroj, ktorý určí, či vstupný reťazec obsahuje párne alebo nepárne číslo 1. Stroj by mal dať ako výstup 1, ak je v reťazci párny počet 1 a v opačnom prípade 0.

Riešenie:

Mooreov stroj bude:

Mooreov stroj

Toto je požadovaný stroj Moore. V tomto stroji stav q1 akceptuje nepárny počet 1 a stav q0 akceptuje párny počet 1. Počet núl nie je obmedzený. Preto pre vstup 0 je možné použiť vlastnú slučku na oba stavy.

Príklad 5:

Navrhnite Mooreov stroj so vstupnou abecedou {0, 1} a výstupnou abecedou {Y, N}, ktorá produkuje Y ako výstup, ak vstupná sekvencia obsahuje 1010 ako podreťazec, inak produkuje N ako výstup.

Riešenie:

Mooreov stroj bude:

Mooreov stroj