logo

Stroj Moore

Moorov stroj je končni avtomat, v katerem se o naslednjem stanju odločata trenutno stanje in trenutni vhodni simbol. Izhodni simbol v danem času je odvisen samo od trenutnega stanja stroja. Moorov stroj je mogoče opisati s 6 tuplemi (Q, q0, ∑, O, δ, λ), kjer je

 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 

Primer 1:

Diagram stanja za Moore Machine je

Stroj Moore

Prehodna tabela za Moore Machine je:

pretvarjanje niza v datum
Stroj Moore

V zgornjem Moorovem stroju je izhod predstavljen z vsakim vhodnim stanjem, ločenim z /. Izhodna dolžina za Moorov stroj je večja od vhodne za 1.

Vnos: 010

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

Izhod: 1110 (1 za q0, 1 za q1, spet 1 za q1, 0 za q2)

Primer 2:

Oblikujte Moorov stroj za generiranje komplementa 1 danega binarnega števila.

rešitev: Za ustvarjanje komplementa 1 danega binarnega števila je preprosta logika, da če je vhod 0, bo izhod 1 in če je vhod 1, bo izhod 0. To pomeni, da obstajajo tri stanja. Eno stanje je začetno stanje. Drugo stanje je za sprejemanje 0 kot vhod in ustvarjanje izhoda kot 1. Tretje stanje je za sprejemanje 1 kot vhod in ustvarjanje izhoda kot 0.

csma in csma cd

Zato bo Moorov stroj,

Stroj Moore

Na primer, vzemite eno binarno število 1011

Vnos 1 0 1 1
Država q0 q2 q1 q2 q2
Izhod 0 0 1 0 0

Tako dobimo 00100 kot komplement 1 od 1011, lahko zanemarimo začetno 0 in rezultat, ki ga dobimo, je 0100, ki je komplement 1 od 1011. Tabela transakcij je naslednja:

Stroj Moore

Tako je Moorov stroj M = (Q, q0, ∑, O, δ, λ); kjer je Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. prehodna tabela prikazuje funkciji δ in λ.

Primer 3:

Načrtujte Moorov stroj za binarno vhodno zaporedje tako, da če ima podniz 101, izhod stroja A, če ima vhod podniz 110, izhod B, drugače pa C.

rešitev: Za načrtovanje takega stroja bomo preverili dva pogoja, in sicer 101 in 110. Če dobimo 101, bo izhod A, če prepoznamo 110, pa bo izhod B. Za druge nize bo izhod C.

Delni diagram bo:

Stroj Moore

Zdaj bomo vstavili možnosti 0 in 1 za vsako stanje. Tako Moorov stroj postane:

uporabo interneta
Stroj Moore

Primer 4:

Konstruirajte Moorov stroj, ki določa, ali vhodni niz vsebuje sodo ali liho število 1. Stroj mora dati 1 kot izhod, če je v nizu sodo število 1, sicer pa 0.

rešitev:

Stroj Moore bo:

Stroj Moore

To je potreben stroj Moore. V tem stroju stanje q1 sprejme liho število 1, stanje q0 pa sodo število 1. Število ničel ni omejeno. Zato je za vhod 0 mogoče uporabiti samozanko v obeh državah.

Primer 5:

Načrtujte Moorov stroj z vhodno abecedo {0, 1} in izhodno abecedo {Y, N}, ki proizvede Y kot izhod, če vhodno zaporedje vsebuje 1010 kot podniz, sicer proizvede N kot izhod.

rešitev:

Stroj Moore bo:

Stroj Moore