logo

Moore mašina

Moore'o mašina yra baigtinės būsenos mašina, kurioje kitą būseną lemia esama būsena ir esamos įvesties simbolis. Išvesties simbolis tam tikru metu priklauso tik nuo esamos mašinos būsenos. Moore'o mašiną galima apibūdinti 6 kortelėmis (Q, q0, ∑, O, δ, λ), kur,

 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 

1 pavyzdys:

Moore mašinos būsenos diagrama yra

Moore mašina

Moore mašinos perėjimo lentelė yra:

jfx java pamoka
Moore mašina

Aukščiau pateiktoje Moore mašinoje išvestis vaizduojama su kiekviena įvesties būsena, atskirta /. Moore mašinos išvesties ilgis yra 1 didesnis nei įvesties ilgis.

Įvestis: 010

Perėjimas: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2

Išvestis: 1110 (1 q0, 1 q1, vėl 1 q1, 0 q2)

2 pavyzdys:

Sukurkite Moore mašiną, kuri generuotų duoto dvejetainio skaičiaus 1 komplementą.

Sprendimas: Norint sugeneruoti tam tikro dvejetainio skaičiaus 1 papildinį, paprasta logika yra tokia, kad jei įvestis yra 0, tada išvestis bus 1, o jei įvestis yra 1, tada išvestis bus 0. Tai reiškia, kad yra trys būsenos. Viena būsena yra pradžios būsena. Antroji būsena skirta naudoti 0 kaip įvestį ir sukuria išvestį kaip 1. Trečioji būsena skirta 1 įvestis ir išvestis kaip 0.

Taigi Moore mašina bus

Moore mašina

Pavyzdžiui, tada paimkite vieną dvejetainį skaičių 1011

jei kitaip jei kitaip java
Įvestis 1 0 1 1
valstybė q0 2 k q1 2 k 2 k
Išvestis 0 0 1 0 0

Taigi 00100 gauname kaip 1011 papildinį, galime nepaisyti pradinio 0, o gaunamas išėjimas yra 0100, kuris yra 1011 papildinys. Operacijų lentelė yra tokia:

Moore mašina

Taigi Mūro mašina M = (Q, q0, ∑, O, δ, λ); kur Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. perėjimų lentelėje parodytos δ ir λ funkcijos.

3 pavyzdys:

Suprojektuokite Moore mašiną dvejetainei įvesties sekai taip, kad jei ji turi poeilelę 101, mašinos išvestis A, jei įvestis turi poeilelę 110, ji išvestų B, priešingu atveju išvestų C.

Sprendimas: Kurdami tokią mašiną, patikrinsime dvi sąlygas, kurios yra 101 ir 110. Jei gausime 101, išvestis bus A, o jei atpažinsime 110, išvestis bus B. Kitoms eilutėms išvestis bus C.

Dalinė diagrama bus tokia:

Moore mašina

Dabar kiekvienai būsenai įterpsime 0 ir 1 galimybes. Taigi Moore mašina tampa:

Moore mašina

4 pavyzdys:

Sukurkite Moore mašiną, kuri nustato, ar įvesties eilutėje yra lyginis ar nelyginis 1 skaičius. Įrenginys turėtų pateikti 1 kaip išvestį, jei eilutėje yra lyginis skaičius 1, o kitu atveju - 0.

Sprendimas:

Moore mašina bus:

Moore mašina

Tai reikalinga Moore mašina. Šioje mašinoje būsena q1 priima nelyginį skaičių 1, o būsena q0 – lyginį skaičių 1. Nulių skaičiaus apribojimų nėra. Taigi, kai įvestis yra 0, savaiminė kilpa gali būti taikoma abiejose būsenose.

kampinė medžiaga

5 pavyzdys:

Sukurkite Moore mašiną su įvesties abėcėle {0, 1} ir išvesties abėcėle {Y, N}, kuri sukuria Y kaip išvestį, jei įvesties sekoje yra 1010 kaip poeilutė, kitu atveju ji sukuria N kaip išvestį.

Sprendimas:

Moore mašina bus:

Moore mašina