Mealy machines in terms of sequential circuit

<< Equivalent machines

Regular languages, Complement of a language >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 23

Reading Material

Introduction to Computer Theory

Chapter 8

Summary

Mealy machines in terms of sequential circuit

Example

Consider the following sequential circuit

output

input

DELAY

NAND

AND

The following four types of boxes are used in this circuit

NAND box (NOT AND): For the given input, it provides the complement of Boolean AND output.

DELAY box (Flip Flop box): It delays the transmission of signal along the wire by one step (clock pulse).

OR box: For the given input, it provides the Boolean OR output.

AND box: For the given input, it provides the Boolean AND output.

The current in the wire is indicated by 1 and 0 indicates the absence of the current.

There are two points A and B w.r.t. to which following four states of the machine are identified according to the

presence and absence of current at these points i.e.

q0(A=0, B=0) ∫ (0,0)

q1 (A=0, B=1) ∫ (0,1)

q2 (A=1, B=0) ∫ (1,0)

q3 (A=1, B=1) ∫ (1,1)

The operation of the circuit is such that the machine changes its state after reading 0 or 1. The

transitions are determined using the following relations

new B = old A

new A = (input) NAND (old A AND old B)

output = (input) OR (old B)

It is to be noted that old A and old B indicate the presence or absence of current at A and B before inputting any

letter. Similarly new A and new B indicate the presence or absence of current after reading certain letter.

At various discrete pulses of a time clock, input is received by the machine and the corresponding output string

is generated.

The transition at the state q0 after reading the letter 0, can be determined, along with the corresponding output

character as under

new B = old A = 0

new A = (input) NAND (old A AND old B)

= 0 NAND ( 0 AND 0) = 0 NAND 0

output = (input) OR (old B) = 0 OR 0 = 0

Thus after reading 0 at q0 new B is 0 and new A is 1 i.e. machine will be at state (1,0) ∫ q2 and during this

process it's output character will be 0.

The remaining action of this sequential circuit can be determined as shown by the following suggested transition

table of the corresponding Mealy machine

Theory of Automata

(CS402)

Inputting 0

Inputting 1

Old state

State

Output

State

Output

q0 ∫(0,0)

(1,0)∫q2

q1 ∫(0,1)

(1,0)∫q2

q2 ∫(1,0)

(1,1)∫q3

q3 ∫(1,1)

(0,1)∫q1

(1,1)∫q3

The corresponding transition diagram may be as follows

0/0, 1/1

0/1

0/1 1/1

1/1

Note: It may be noted that if the string 00 is read at any state, it results in ending in state q3.

Running the string 01101110 on the previous machine, the output string can be determined by the following

table

Input

States

output

Following is a note regarding the sequential circuit under consideration

Note

input

output

DELAY

NAND

AND

It is to be noted that in this sequential circuit, delay box plays an important role in introducing four states of the

machine.

Table of Contents: