The values of the output function F(t) in the most general case is a
function of the present state q(t) and present input x(t).
F t
q t x t
( )
( ( ), ( ))
= λ
where λ is called the output function.
This model is called the “Mealey machine”.
A “Mealey machine” is a six-tuple ( , , , , , )
Q O
q
Σ δ λ 0 where all the symbols
except λ have the same meaning as discussed in the sections above.
λ is the output function mapping Σ × Q into O.
1.6.3 Moore Machine
If the output function F(t) depends only on the present state and is independent
of the present input q(t), then we have the output function f(t) given by
F t
q t
( )
( ( ))
= λ
A Moore machine is a six-tuple ( , , , , , )
Q O
q
Σ
δ λ 0 with the usual
meanings for symbols.
Ì Exam ple 1.6.1: Given state table as shown below that describes a
finite-state machine with states Q q q q q
= { , , , },
0
1
2
3
input alphabet
Σ = { , }
01 and output alphabet O = {0, 1}, sketch the state diagram.
δ
λ
State
Input
Out put
0
1
0
1
q 0
q 1
q 0
1
0
q 1
q 3
q 0
1
1
q 2
q 1
q 2
0
1
q 3
q 2
q 1
0
0
Solu tion
The given state table corresponds to finite-state machine with output. The
corresponding state diagram is shown below.
90
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 2
q 3
1,1
0,1
0,0
0,0
1,0
0,1
1,0