logo

Moore-machine

Moore-machine is een eindige toestandsmachine waarin de volgende toestand wordt bepaald door de huidige toestand en het huidige invoersymbool. Het uitvoersymbool op een bepaald moment hangt alleen af ​​van de huidige toestand van de machine. Moore-machine kan worden beschreven door 6 tupels (Q, q0, ∑, O, δ, λ) waarbij,

 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 

Voorbeeld 1:

Het toestandsdiagram voor Moore Machine is

Moore-machine

Overgangstabel voor Moore Machine is:

discrete wiskunde-ontkenning
Moore-machine

In de bovenstaande Moore-machine wordt de uitvoer weergegeven met elke invoerstatus gescheiden door /. De uitvoerlengte voor een Moore-machine is 1 groter dan de invoer.

Invoer: 010

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

Uitgang: 1110(1 voor q0, 1 voor q1, nogmaals 1 voor q1, 0 voor q2)

Voorbeeld 2:

Ontwerp een Moore-machine om 1-complement van een bepaald binair getal te genereren.

Oplossing: Om het 1-complement van een bepaald binair getal te genereren, is de eenvoudige logica dat als de invoer 0 is, de uitvoer 1 zal zijn en als de invoer 1 is, de uitvoer 0 zal zijn. Dat betekent dat er drie toestanden zijn. Eén status is de startstatus. De tweede toestand is voor het nemen van nullen als invoer en het produceren van uitvoer als 1. De derde toestand is voor het nemen van enen als invoer en het produceren van uitvoer als 0.

Daarom zal de Moore-machine zijn:

Moore-machine

Neem dan bijvoorbeeld één binair getal 1011

Invoer 1 0 1 1
Staat Q0 Q2 q1 Q2 Q2
Uitvoer 0 0 1 0 0

We krijgen dus 00100 als 1-complement van 1011, we kunnen de initiële 0 verwaarlozen en de output die we krijgen is 0100, wat het 1-complement van 1011 is. De transactietabel is als volgt:

Moore-machine

Dus Moore-machine M = (Q, q0, ∑, O, δ, λ); waarbij Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. de transitietabel toont de δ- en λ-functies.

mysql toon alle gebruikers

Voorbeeld 3:

Ontwerp een Moore-machine voor een binaire invoerreeks, zodat als deze een substring 101 heeft, de machine uitvoer A, als de invoer substring 110 heeft, deze B uitvoert en anders C uitvoert.

Oplossing: Voor het ontwerpen van zo'n machine zullen we twee voorwaarden controleren, en dat zijn 101 en 110. Als we 101 krijgen, zal de uitvoer A zijn, en als we 110 herkennen, zal de uitvoer B zijn. Voor andere strings zal de uitvoer zijn C.

Het gedeeltelijke diagram wordt:

Moore-machine

Nu zullen we voor elke toestand de mogelijkheden van nullen en enen invoegen. Zo wordt de Moore-machine:

ex van gebruikersnaam
Moore-machine

Voorbeeld 4:

Construeer een Moore-machine die bepaalt of een invoerreeks een even of oneven aantal 1-en bevat. De machine moet 1 als uitvoer geven als er een even aantal 1-en in de string staat, en anders 0.

Oplossing:

De Moore-machine zal zijn:

Moore-machine

Dit is de vereiste Moore-machine. In deze machine accepteert toestand q1 een oneven aantal enen en toestand q0 accepteert een even aantal enen. Er is geen beperking op het aantal nullen. Daarom kan voor 0-invoer een zelflus op beide toestanden worden toegepast.

Voorbeeld 5:

Ontwerp een Moore-machine met het invoeralfabet {0, 1} en het uitvoeralfabet {Y, N} die Y als uitvoer produceert als de invoerreeks 1010 als substring bevat, anders produceert het N als uitvoer.

Oplossing:

De Moore-machine zal zijn:

Moore-machine