DHARM
REGULAR EXPRESSIONS 239
sequence of transitions between states is responsible for generating the output. For example,
a finite automata shown in Fig. 9.33 whose start state is A, and states A, B and C are represented
equivalently by the symbol 0, 0 and 1 respectively.
B C
b a, b
A
a
b
a
001
Fig. 9.33
Then for the input string ‘abba’ the output string will be determine as follows,
From the start state A, following sequence of states is obtained after processing the
complete string ‘abba’,
A B C C C
abba
00111
Input string
Output string
Corresponding to that sequence of states we obtain the output string 00111.
9.6.2.1 Definition
A Moore machine is defined as following set of tuples,
- A finite set of states Q,
- A finite set of input Symbols Σ,
- A finite set of output Symbols ∆,
- Transition function δ,
- Output function λ,
- Starting state r 0 where r 0 ∈ Q.
Let Mo is a Moore machine, then it can be defined using above tuples as,
Mo = (Q, ΣΣΣΣΣ, ∆∆∆∆∆, δδδδδ, λλλλλ, r 0 )
where, transition function δ is defined as,
δ : Q × Σ → Q
which is the partial mapping of a state (∈ Q)with an input symbol (∈ Σ) that return a state
(∈ Q). Similarly the output function λ, is defined as,
λ : Q → ∆
which is the direct mapping between the state and the output symbol.
For example, consider a Moore machine Mo shown in Fig. 9.34.
r 0
1
1
0
0
0
r 1 r 2
1
Fig. 9.34 Mo.
