logo

Moore maskin

Moore-maskin er en endelig tilstandsmaskin der neste tilstand bestemmes av gjeldende tilstand og gjeldende inngangssymbol. Utgangssymbolet på et gitt tidspunkt avhenger kun av maskinens nåværende tilstand. Moore-maskinen kan beskrives med 6 tupler (Q, q0, ∑, O, δ, λ) hvor,

 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 

Eksempel 1:

Tilstandsdiagrammet for Moore Machine er

Moore maskin

Overgangstabell for Moore Machine er:

java-strengformat langt
Moore maskin

I Moore-maskinen ovenfor er utgangen representert med hver inngangstilstand atskilt med /. Utgangslengden for en Moore-maskin er 1 større enn inndata.

Inndata: 010

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

Produksjon: 1110(1 for q0, 1 for q1, igjen 1 for q1, 0 for q2)

Eksempel 2:

Design en Moore-maskin for å generere 1-komplement av et gitt binært tall.

Løsning: For å generere 1-komplement av et gitt binært tall er den enkle logikken at hvis inngangen er 0 så vil utgangen være 1 og hvis inngangen er 1 så vil utgangen være 0. Det betyr at det er tre tilstander. En tilstand er starttilstand. Den andre tilstanden er for å ta 0-er som input og produserer utdata som 1. Den tredje tilstanden er for å ta 1-er som input og produsere utgang som 0.

Derfor vil Moore-maskinen være,

Moore maskin

Ta for eksempel ett binært tall 1011 da

Inndata 1 0 1 1
Stat q0 q2 q1 q2 q2
Produksjon 0 0 1 0 0

Dermed får vi 00100 som 1s komplement av 1011, vi kan neglisjere den initiale 0 og utgangen som vi får er 0100 som er 1s komplement til 1011. Transaksjonstabellen er som følger:

Moore maskin

Moore maskin M = (Q, q0, ∑, O, δ, λ); hvor Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. overgangstabellen viser δ- og λ-funksjonene.

string.valueof

Eksempel 3:

Design en Moore-maskin for en binær inngangssekvens slik at hvis den har en delstreng 101, vil maskinens utgang A, hvis inngangen har delstrengen 110, gir den ut B ellers sender den ut C.

Løsning: For å designe en slik maskin vil vi sjekke to forhold, og det er 101 og 110. Hvis vi får 101, vil utgangen være A, og hvis vi gjenkjenner 110, vil utgangen være B. For andre strenger vil utgangen være C.

Deldiagrammet vil være:

Moore maskin

Nå skal vi sette inn mulighetene for 0-er og 1-er for hver tilstand. Dermed blir Moore-maskinen:

java arraylist sortert
Moore maskin

Eksempel 4:

Konstruer en Moore-maskin som bestemmer om en inndatastreng inneholder et partall eller et oddetall på 1-er. Maskinen skal gi 1 som utgang hvis et partall på 1 er i strengen og 0 ellers.

Løsning:

Moore-maskinen vil være:

Moore maskin

Dette er den nødvendige Moore-maskinen. I denne maskinen aksepterer tilstand q1 et oddetall på 1-ere og tilstand q0 aksepterer partall på 1-ere. Det er ingen begrensning på antall nuller. For 0-inngang kan derfor selvsløyfe brukes på begge tilstandene.

Eksempel 5:

Design en Moore-maskin med input-alfabetet {0, 1} og output-alfabetet {Y, N} som produserer Y som utdata hvis input-sekvensen inneholder 1010 som en understreng ellers produserer den N som utdata.

Løsning:

Moore-maskinen vil være:

Moore maskin