Transcript Finite Automata (FA) with Output

Finite Automata (FA) with
Output





FA discussed so far, is just associated with
R.Es or language.
Is there exist an FA which generates an
output string corresponding to each input
string ?
The answer is yes.
Such machines are called machines with
output.
There are two types of machines with output.
Moore and Mealy machines.
1
Moore Machine

Created by E.F Moore in 1956.
To Design a mathematical model for sequential circuits.
A state machine that determines its outputs from the present state only.
Moore machines is a Collection of Five Things
1) A finite set of states q0, q1, q2, … where q0 is the initial state.
2) An alphabet of letters ∑ = {a,b,c,…} from which the input strings are
formed.
3) An alphabet Г ={x,y,z,…} of output characters from which output
strings are generated.
4) δ: Transition function.

5) λ: output function. It depends on the state only. (λ= Q Г )







2
Example-1

Consider the following Moore machine having the states q0, q1,
q2, q3 where q0 is the start state and ∑= {a,b}, and Г={0,1}
the transition table follows as
Transition Table
3
Example-2
Input String = abbabbba
Output String =100010101
Pictorial Representation of
Previous Moore Machine
Output can be determined by the following table
It may be noted that the length of output string is l more than that of input
string as the initial state prints out the
extra character 1, before the input string is read
4
Sequential circuit
(Block Diagram)
Depends on the
Current State
Next State
Input
Next State
Logic
Current State
State
Register
Output
Logic
Clock
5
Example-2 (A D-Flip flop type
Moore Machine

Consider the following Moore machine having the states A,B
where A is the start state and ∑= {0,1}, and Г={0,1}
the transition table follows as
Old States
New States after Reading
input Symbols
Character to be
printed
0
1
A
A
B
0
B
A
B
1
1
0
A/0
1
0
Moore Machine State Diagram
B/1
6
Mealy Machine

Created by G.H Mealy in 1955.
A state machine that determines its outputs from the present state and
from the inputs.
Mealy machines is a Collection of Five Things
1) A finite set of states q0, q1, q2, … where q0 is the initial state.
2) An alphabet of letters ∑ = {a,b,c,…} from which the input strings are
formed.
3) An alphabet Г ={x,y,z,…} of output characters from which output
strings are generated.
4) δ: Transition function.

5) λ: output function. It depends on the input and state. (λ= Qx ∑  Г )

All transitions are in the form i/o (input symbol/output character).






7
Example-1

Consider the following Mealy machine having the states q0, q1,
q2, q3 where q0 is the start state and ∑= {a,b}, and Г={0,1}
Input String= abbabbba
Output String=01111010

It may be noted that in Mealy machine, the length of output string
is equal to that of input string
8

Considered as a state machine, the turnstile has two
states: Locked and Unlocked.[2] There are two inputs that affect its
state: putting a coin in the slot (coin) and pushing the arm (push). In
the locked state, pushing on the arm has no effect; no matter how
many times the input push is given, it stays in the locked state. Putting
a coin in – that is, giving the machine a coin input – shifts the state
from Locked to Unlocked. In the unlocked state, putting additional
coins in has no effect; that is, giving additional coin inputs does not
change the state. However, a customer pushing through the arms,
giving a push input, shifts the state back to Locked.
Example-2 (Serial Adder)

Consider the following Mealy machine having two states q0, q1 where q0 is
the start state and ∑= {00,01,10,11}, and Г={0,1}
00 / 0
Start
10 / 0
11 / 0
q0
q1
01 / 0
00 / 1
01 / 1
10 / 1
11 / 1


q0 corresponds to No-carry State and q1 corresponds to a carry State.
In case of last bits, when there is 1 carry but you
11001
are not getting any input at q1, so u will consider the
10101 +
00 as input, it will output 1 and you will reach at
----------State q0.
101110
10
Complementing Machine

Consider the following Mealy machine having only one state q0
∑= {0,1}, and Г={0,1}
the transition table follows as

If 0011010 is run on this machine then the corresponding output
string will be 1100101.
This machine is called Complementing machine.

11
Equivalent Machines



Two machines are said to be equivalent if they print the
same output string when the same input string is run
on them.
Two Moore machines may be equivalent. Similarly two
Mealy machines may also be equivalent.
But a Moore machine can’t be equivalent to any Mealy
machine. However, ignoring the extra character printed
by the Moore machine, there exists a Mealy machine
which is equivalent to the Moore machine.
12
Theorem-1
Statement

For every Moore machine there is a Mealy machine that is
equivalent to it (ignoring the extra character printed by the Moore
machine).
Proof:

Let M be a Moore machine, then shifting the output characters
corresponding to each state to the labels of
corresponding incoming transitions, machine thus obtained will be
a Mealy machine equivalent to M.
Note: (It may be noted that while converting a Moore machine into
an equivalent Mealy machine, the output character of a state will
be ignored if there is no incoming transition at that state. A loop at
a state is also supposed to be an incoming transition).
13
Example
Moore Machine:
Mealy Machine:
14
Example


Running the string “abbabbba” on both the machines,
the output string can be determined by the following
table
Same output is generated by both machines by ignoring the first
output of Moore machine.
15
Theorem-2
Statement

For every Mealy machine there is a Moore machine that is equivalent to it
(ignoring the extra character printed the Moore machine).
Proof:






Let M be a Mealy machine. At each state there are two possibilities for incoming
transitions, The incoming transitions have the same output character.
The incoming transitions have different output characters.
If all the transitions have same output characters, then shift that character to the
corresponding state.
If all the transitions have different output characters, then the state will be
converted to as many states as the number of different output characters for
these transitions, which shows that if this happens at state qi then qi will be
converted to qi 1 and qi2 i.e. if at qi there are the transitions with two output
characters then qi1 for one character and qi2 for other character.
Shift the output characters of the transitions to the corresponding new states qi 1
and qi2. Moreover, these new states qi1 and qi2 should behave like qi as well.
Continuing the process, the machine thus obtained, will be a Moore machine
equivalent to Mealy machine M.
16
Note about Theorem-2
Note:
 It may be noted that if there is no incoming transition at
certain state then any of the output characters may be
associated with that state.
 It may also be noted that if the initial state is converted
into more than one new states then only one of these
new states will be considered to be the initial state.
17
Example:
Mealy Machine:

Shifting the output character 1 of transition b to q0
18
Example (Continued….)

Shifting the output character 0 of transition a to q1

Shifting the output character 1 of transition b to q2
19
Example (Continued….)

Splitting q3 into q31 and q32
20
Example (Continued….)


Running the string “abbabbba” on both the machines, the output
strings can be determined by the following table
Same output is generated by both machines by ignoring the first
output of Moore machine.
21
Applications






The various flip-flops, counters and shift registers are all
examples of sequential machines (automatons).
All these circuits contain memory elements.
The flip-flops are the elementary memory elements. The
counters and shift registers are composed of more than one
such element.
All the circuits are capable of assuming more than one
state.
Their outputs do not depend only on the inputs but also on
the state in which the circuit is at the time when the input is
acting on it.
If we note carefully the circuits of all these elements, they
have a feedback from the output to the input.
22
The serial binary adder or bit-serial adder is
a digital circuit that performs binary addition bit
by bit. The serial full adder has three single-bit
inputs for the numbers to be added and the
carry in. There are two single-bit outputs for the
sum and carry out. The carry-in signal is the
previously calculated carry-out signal. The
addition is performed by adding each bit, lowest
to highest, one per clock cycle.

THANKS