<<

. 4
( 9)



>>

b s3 b
a s4



(4) Find the minimal automaton which accepts the same language as the
automaton

a

a,b
a s1 b
s0
s3
b a
s2

b


(5) Find the minimal automaton which accepts the language described by
aa— (b ∨ c).
(6) Find the minimal automaton which accepts the language described by
a(b ∨ c)— bb— .
(7) Find the minimal automaton which accepts the language described by
(abc)— (b ∨ c).
(8) Find the minimal automaton which accepts the language described by
(a ∨ bc)c(ab)— .
(9) Find the syntactic monoid of the language accepted by the automaton


a a,b

a
b b
s0 s1 s2 s3
b
a
Automata
84


(10) Find the syntactic monoid of the language accepted by the automaton
a
s1
a
s0 b
b
b s2
a
(11) Find the syntactic monoid of the language accepted by the automaton
a
a a b
s2
s1
s0 b b

(12) Find the syntactic monoid of the language accepted by the automaton
a b

a b
s0 s1 s2


(13) Find the syntactic monoid of the language accepted by the automaton
b
s3
s1
a a
s0 b
b
s4
s2
b
a



3.4 Pumping Lemma for regular languages
We now show that certain languages are not regular languages. To do so we
¬rst prove a lemma known as the Pumping Lemma.
Lemma 3.5 (Pumping Lemma) Let L be an in¬nite regular language. There
exists a constant n such that if z ∈ L and |z| > n, then there exists u, v, w ∈ — ,
v = » such that z = uvw and uv k w ∈ L for all k ≥ 0. The length of the string
uw is less than or equal to n. Further if M is an automaton accepting the
language L and M has q states, then n < q. It is possible to have the stronger
statement that z = uvw where the length of uv is less than or equal to q.
Proof Let L be accepted by the automaton M = ( , Q, s0 , ’, F). Let
’(si , ai ) = si+1 for i = r to t; denote this by

(s1 , ar a2 a3 . . . at ) (st+1 , »).
3.4 Pumping Lemma for regular languages 85


Since L contains a word of length m, where m > q, say w = a1 a2 a3 . . . am .
Note that if (s1 , a1 a2 a3 . . . am ) — (sm , »), then sm is an acceptance state. Since
m > q, in reading w, M must pass through the same state twice. Therefore
(s1 , a1 a2 a3 . . . a j’1 ) — (sk , ») and (s1 , a1 a2 a3 . . . ak’1 ) — (sk , ») = for some
j < k and both
— —
(s j , a j a j+1 . . . am ) (sm , ») (s j , ak ak+1 . . . am ) (sm , »).
and

Thus
— —
(s1 , a1 a2 a3 . . . am ) (sm , ») and (s1 , a1 a2 . . . a j’1 ak ak+1 . . . am ) (sm , »).

Also (s j , a j a j+2 . . . ak’1 ) s j , so in reading a j a j+2 . . . ak’1 , M returns to the
same state and

(s1 , a1 a2 . . . a j’1 (a j a j+2 . . . ak’1 )n ak ak+1 . . . am ) (sm , »).

Letting u = a1 a2 . . . a j’1 , v = a j a j+2 . . . ak’1 , and w = ak ak+1 . . . am , we
have uv n w ∈ L for n ≥ 0.
Since |uw| < |uvw| = m, if |uw| > q, we can repeat this process on uv
until eventually we have u (v )n w ∈ L for n ≥ 0 where |u w | < q. Let v be
the ¬rst cycle in z produced by the same state being passed through twice when
the automaton is reading z. Then the length of uv is less than or equal to q.
Note that it is no longer true that the length of uw is less than q.

Using this lemma, we have the following theorem:

Theorem 3.9 The language L = {a n bn : n ≥ 1} is not regular.


Proof Assume L = {a n bn : n ≥ 1} is regular. Since L is in¬nite, there exist
strings u, v, w ∈ — , v = » such that uv — w ⊆ L. There are three possibili-
ties. First u = a m’k , v = a k , and w = bm for some m. But then a m’k a 2k bm =
a m+k bm ∈ L, which is a contradiction. Second, u = a m , v = bk , and w = bm’k .
By a similar argument, we reach a contradiction. Third u = a m’k , v = a k br , and
w = bm’r . But then a m’k a k br a k br bm’r ∈ L, which is a contradiction. Hence
L is not regular.

Exercises
For each of the following sets, determine if the set is regular. If it is, describe the
set with a regular expression. If it is not a regular set, use the Pumping lemma
to show that it is not.

(1) {a 2n bn : n ≥ 1}.
Automata
86


{a n b2n a n : n ≥ 1}.
(2)
{(ab)n : n ≥ 1}.
(3)
{a n bn a n : n ≥ 1}.
(4)
{a n bm : m, n ≥ 1}.
(5)
{ww : w ∈ — and | | = 2}.
(6)
{a 2n : n ≥ 1}.
(7)
{w ∈ {a, b}— : w contains an equal number of as and bs}.
(8)
{w ∈ {a, b}— : w contains exactly four bs}.
(9)
{ww R : w ∈ {a, b}— and the length of w is less that or equal to three}.
(10)
{ww R : w ∈ {a, b}— .
(11)
{wcw R : w ∈ {a, b, c}— .
(12)
{w w : w ∈ (0, 1)— and w is the 1s complement of w}.
(13) ¯ ¯

{w ∈ {a, b, c} : the length of w = n 2 : n ≥ 1}.
(14)
{w ∈ {a, b, c}— : the length of w ≥ n for some n ≥ 1}.
(15)
{w ∈ {a, b}— : w contains more as than bs}.
(16)



3.5 Decidability
In this section we answer the questions

(1) Is there an algorithm for determining whether the language accepted by a
¬nite automaton is empty?
(2) Is there an algorithm for determining whether two ¬nite automata accept
the same language?
(3) Is there an algorithm for determining whether two regular languages are
the same?
(4) Is there an algorithm for determining whether a language accepted by an
automaton is in¬nite?

The key to all of these questions is that they require the algorithm to be able
to provide a yes or no answer. We are not concerned with the ef¬ciency of the
algorithm but only if within some ¬nite length of time the algorithm can answer
the question. Note that if an algorithm can determine that a statement is true (or
false) within some bounded length of time, then the algorithm can determine
whether the statement is true.
We begin with a proof of the ¬rst question although we can see that if we
can answer the second question, then we can answer the ¬rst question. Given a
language L, as an expression, we simply determine the automaton that accepts
L and see if the language accepted is empty.
3.5 Decidability 87


Theorem 3.10 There is an algorithm for determining whether the language
M(L) accepted by a ¬nite automaton is empty.

Proof Let M(L) have n states. Then M(L) is empty if and only if s0 is not an
acceptance state and no string of length less than n is accepted since the shortest
string accepted by M(L) cannot enter a state twice. Since there are only a ¬nite
number of these strings, they can be checked.

Theorem 3.11 There is an algorithm for determining whether two ¬nite
automata accept the same language.

Proof We already know that given automata M1 and M2 accepting languages
M1 (L) and M2 (L), respectively, we can construct automata for accepting
languages M1 (L) © M2 (L), and M1 (L) ∪ M2 (L). Combining these construc-
tions, we can ¬nd an automaton which accepts (M1 (L) © M2 (L) ) ∪ (M2 (L) ©
M1 (L) ), the symmetric difference of M1 (L) and M2 (L). But this set is empty if
and only if M1 (L) = M2 (L). Hence we use the previous theorem to determine
whether (M1 (L) © M2 (L) ) ∪ (M2 (L) © M1 (L) ) is empty.

Theorem 3.12 There is an algorithm for determining whether two regular
languages are the same.

Proof Given expressions for L 1 and L 2 , ¬nd the automata M1 and M2 so that
L 1 = M1 (L) and L 2 = M2 (L). Now use the previous theorem to see if the two
automata accept the same language.

Before proving the next theorem, we need the following lemma.

Lemma 3.6 Assume that an automaton M has n states. The language L
accepted by M is in¬nite if and only if there is a word in L whose length
is greater than n and less than 2n.

Proof First assume L is in¬nite. By the Pumping Lemma there exists uv m w ∈
L for all m ≥ 0. Further if M is an automaton accepting the language L and
M has n states, then |uw|, the length of the string uw, is less than or equal to
n. Assume that after u is read, the machine is in state s. If while reading v,
the machine returns to s, let v be the string that is read when the machine ¬rst
returns to s and v x = v. Thus if we have
— — —
(s0 , uvw) (s, vw) (s, w) (s2 , »),

replace it with
— — —
(s0 , uv w) (s, v w) (s, w) (s2 , »).
Automata
88


Thus M reads the string s0 , u(v )n w for any nonnegative integer n. If while
reading v , a state t is repeated, remove all of the states including one of the
ts as well as the letters in v that were read in this cycle. Thus we are simply
removing all cycles in v . Call this string v . Since reading v uses no repeated
states except s, the length of v is less than or equal to n. Thus the length of
uv w is less than or equal to 2n. If the length of uv w is less than or equal
to n, there exists a least integer m so that the length of u(v )n w is greater
than n. Since the length of v is less than n, the length of u(v )m w is less
than 2n.
Conversely in the proof of the Pumping Lemma, we showed that if there is
a word in the language with length m greater than n, then for every positive
integer r , the word uvr w ∈ L, where v is nonempty. Hence L is in¬nite.

Theorem 3.13 There is an algorithm for determining whether a language
accepted by an automaton is in¬nite.

Proof Let M have n states. Then M(L) is in¬nite if and only if M accepts a
string s with n ¤ |s| ¤ 2n. Since there are only a ¬nite number of such words,
check each of them to see if they are accepted by the automata.

Theorem 3.14 There is an algorithm for determining whether a language is
¬nite.

Proof Using the proof of the previous theorem, if there is no string s accepted
by M, with n ¤ |s| ¤ 2n, then M(L) is ¬nite (where we include the empty set
and the set containing only the empty word as ¬nite sets).

Theorem 3.15 There is an algorithm determining whether a language L 1 ⊆
L 2.

Proof We already know that there is an automaton that accepts L 1 © L 2 , which
is empty if and only if L 1 ⊆ L 2 .


Exercises
(1) Prove there is an algorithm for determining if regular language M(L) =

.
(2) Prove there is an algorithm for determining if a regular language M(L)
contains a word that contains a given letter of the alphabet.
(3) Prove there is an algorithm for determining if every letter in the alphabet is
contained in some word in a regular language L.
3.6 Pushdown automata 89


(4) Prove that for a positive integer n, there is an algorithm for determining if
a regular language contains a word with length less than n that contains a
given letter of the alphabet.
(5) Prove that for a positive integer n, there is an algorithm for determining if
every letter in the alphabet is contained in some word with length less than
n in a regular language L.
(6) Prove there is an algorithm for determining if a regular language contains
a word that begins with a given letter of the alphabet.
(7) Prove there is an algorithm for determining if there is a word in a regular
language L of even length.
(8) Prove that for any integer k there is an algorithm for determining if there is
a word in a regular language L of length mk for some m.
(9) Prove that for a regular language L, it is possible to determine if — ’ L is
¬nite.



3.6 Pushdown automata
In the previous section we mentioned that the set {a n bn : n is a positive integer}
is not a regular language. Therefore it cannot be accepted by an automaton.
Intuitively, the problem is that after the automaton has read the as in a word,
it cannot remember how many it has read, so it does not know how many
bs it should read. The automaton basically needs a memory so that it can
remember the letters it has read. A pushdown automaton or PDA is essentially
an automaton together with a very simple memory. The memory is called a
pushdown stack. Associated with the stack is a set of symbols called the stack
symbols. A stack symbol may be placed on the stack. This process is called
pushing the symbol onto the stack. If x is a stack symbol, then push x simply
means x is placed on the stack. The top symbol may also be removed from the
stack. This is the last symbol placed on the stack. Since the last symbol placed
in the stack is the ¬rst out, the stack is said to have the LIFO (last in“¬rst out)
property. Thus the symbols are removed from the stack in reverse order from
the order they were put in the stack. The process of removing the top symbol
from the stack is called popping the stack. If x is a stack symbol then pop x
simply means that when the stack is popped, the symbol x is removed if it is
on top of the stack. The purpose of the stack is to allow the PDA to remember
the letters in the word that it has read so that it can duplicate them or replace
them with other letters.
Assume that the word to be read is placed on a tape. The tape is divided
into little squares with the letters of the word in the ¬rst squares. The rest of
Automata
90


the tape is considered to be blank. Since the words may be arbitrarily long, it
is best to use an in¬nite tape. These may have to be custom made. One of the
advantages of mathematics is that mathematical structures do not usually have
to be actually constructed.
The PDA, beginning at the left, reads a letter at a time in the same manner as
a standard automaton. The PDA may read a letter from the tape or pop (remove
from the top) and read a symbol from the stack or both. Depending on its current
state and the symbol(s) read, the PDA may change state, push a symbol in the
stack, or both.

Tape
ababc Stack
a
b
Processor
” A
C



We now de¬ne a PDA more formally.
Let » = ∪ {»} and I » = I ∪ {»}.

De¬nition 3.8 A pushdown automaton is a sextuple

M = ( , Q, s, I, ’, F)

where is a ¬nite alphabet, Q is a ¬nite set of states, s is the initial or starting
state, I is a ¬nite of stack symbols, ’ is the transition relation and F is the set
of acceptance states. The relation ’ is a subset of
»
— Q — I » ) — (Q — I » )).
((

Thus the relation reads a letter from » , determines the state, and reads a
letter from I » . It then changes state or remains in the same state and gives a
letter of I » as output. Similar to the automata, the letter of a word is removed
when it is read. The top letter on the stack is also removed when it is read. As
discussed above, we say it is popped from the top of the stack. The letter of I
produced by the relation is placed on top of the stack or pushed on the stack as
discussed above. A word is accepted by the PDA if and only if after beginning
in the start state, with an empty stack, the word is read, if possible, the machine
is in an acceptance state, and the stack is empty. If all of the above do not occur,
then the word is rejected. The language consisting of all words accepted by the
pushdown automaton M is denoted by M(L).
3.6 Pushdown automata 91


Elements of ’ have the following rules:

((a, s, E), (t, D)) In state s, a is read and E is popped, go to state tand
push D.
((a, s, »), (t, D)) In state s, a is read, go to state t and push D.
((», s, »), (s, D)) In state s, push D.
((a, s, E), (t, »)) In state s, and a is read, pop E and go to state t.
((», s, E), (s, »)) In state s, pop E.
((a, s, »), (t, »)) In state s, read a and go to state t.
((a, s, »), (s, »)) In state s, read a.
((», s, »), (t, »)) Move from state s to state t.

De¬nition 3.9 M is a deterministic PDA if ’ ⊆ (( » — Q — I » ) — (Q —
I » )) has the property that if ((s, a, c), (s , c )) and ((s, a, c), (s , c )) ∈ F then
s = s and c = c .

Note that this de¬nition differs between texts.
Since the requirement that M is a deterministic PDA restricts the languages
that it accepts, we will not consider the deterministic PDA.
Although it seems a severe restriction, any language accepted by a PDA can
be accepted by a PDA with only two states, which we will call s and t. The
automaton leaves the ¬rst state before it reads the ¬rst letter and while the stack
is still empty. The second state is then the terminal state. Often it is simpler or
more convenient to use more states. An example of this will be shown in the
examples.
As with the regular automaton, we will show the PDA graphically. The PDA
will be shown as a ¬‚ow chart using only the instructions start, read, push, pop,
and accept. It will be obvious that the ¬‚ow charts below describe PDAs. We
shall not try to prove that every PDA has a ¬‚ow chart. Each edge of a ¬‚ow chart
has a state associated with it. For example in the following ¬gure, (t) on the
edge indicates that at that point on the chart, we are in state t. We could put
the state with each edge, but we only do so when the state is changed. Thus the
state is determined by the location on the ¬‚ow chart. When only two states are
used, including the start command which takes the PDA to the state t, the state
will not be indicated. The symbol


Start
(t)
Automata
92


indicates start and switch to state t. The symbol

Start

Push
(t) S


indicates start, push S, and switch to state t. The symbol


read

a


indicates read a. The symbol



a
pop


indicates pop a. The symbol

Push a

indicates push a. Finally, the symbol



accept


indicates accept if the word has been read, the machine is in an acceptance state,
and the stack is empty. Thus the diagram

Start
(t)
a a
b a push
pop read
a
accept
3.6 Pushdown automata 93


allows the PDA to read a and then push it or read b and pop a if it is on the stack.
Thus every time a b is read, it removes an a which has been read and placed in
the stack. In this example the alphabet and the stack symbols will both consist
of a, and b. If, at any time, there were more bs read than as in the stack, there
would be no a in the stack to remove and the PDA could not continue. If the
number of as is equal to the number of bs when the word is read, then the stack
will be empty. A word is accepted if, after popping a, the word has been read
and the stack is empty. Therefore this PDA accepts words which have the same
number of as and bs provided that, for every b in the word, the string preceding
it contains more as than bs. For example consider the word aababb. We can
trace its path with the following table:


instruction stack tape
» aababb
start
» ababb
read
push a a ababb
a babb
read
push a aa babb
aa abb
read
a abb
pop
a bb
read
push a aa bb
aa b
read
a b
pop
»
a
read
» »
pop
» »
accept



Example 3.26 The PDA


Start
(t)

a b
b
a
push push
read
a
a b
b pop
pop

b
a
Accept
Automata
94


accepts words containing the same number of as and bs. Consider the word
abba. We can trace its path with the following table:

instruction stack tape
» abba
start
» bba
read
push a a bba
a ba
read
» ba
pop
» a
read
push b b a
»
b
read
» »
pop
» »
accept


In the following example, three states are used. A move to a new state is
indicated in the diagram by an arrow for which there is no loop or are no return
arrows.
Example 3.27 The PDA
Start pop
b
(t)
(s)
b
a
b
a
a a read
pop
push read b
a
(t)
a
b b b pop
push
b
accept

accepts words ww R where w R is the word w reversed. We read the ¬rst half of
the word and then switch states to read the second half of the word. Consider
the word abba. We can trace its path with the following table:

state instruction stack tape
»
s abba
start
»
s bba
read
s push a a bba
s a ba
read
s push b ba ba
t ba a
read
t a a
pop
»
t a
read
» »
t pop
» »
t accept
3.6 Pushdown automata 95


Exercises
(1) Which of the following words are accepted by the following pushdown
automaton M1 ?

Start


a
push
read
a
a
read
b

read
b b
a
pop
read
b
Accept


(a) abbb
(b) aabbb
(c) aabbbbb
(d) aaabbb
(e) aabab
(f) aaabbbb.
(2) Use a table to trace each of the above words through the pushdown automa-
ton M1 .
(3) What is the language accepted by the pushdown automaton M1 ?
(4) Which of the following words are accepted by the following pushdown
automaton M2 ?

Start
(t)

a a b
b pop
pop accept
read read

a a b
push
Automata
96


(a) abb
(b) aabbaaa
(c) aabbbaa
(d) aaabaaa
(e) aabba
(f) aabb.
(5) Use a table to trace each of the above words through the pushdown automa-
ton M2 .
(6) What is the language accepted by the pushdown automaton M2 ?
(7) Which of the following words are accepted by the following pushdown
automaton M3 ?


Start

a
a
read push

a

read

b

pop
a
a
read

a
Accept


(a) abb
(b) aabbaaa
(c) aabbbaa
(d) aaabaaa
(e) aabba
(f) aabb.
(8) Use a table to trace each of the above words through the pushdown automa-
ton M3 .
(9) What is the language accepted by the pushdown automaton M3 ?
(10) Which of the following words are accepted by the following pushdown
automaton M4 ?
3.6 Pushdown automata 97


Start
(t)
a a a
push
b b a
read push push
read
b b
b
a
a
b pop
read read
b
a a b
accept accept

(a) abb
(b) bb
(c) aabbbaaa
(d) abbbaa
(e) aabba
(f) aabb.
(11) Use a table to trace each of the above words through the pushdown automa-
ton M4 .
(12) What is the language accepted by the pushdown automaton M4 ?
(13) Given a pushdown automaton M = ( , Q, s0 , I, ’, F) where = I =
{a, b}, Q = {s0 , s1 , s2 }, F = {s2 }, and ’ has the following relations:
((a, s0 , »), (s1 , a)) In state s0 , a is read, go to state s1 and push a
((b, s0 , »), (s1 , b))
((a, s1 , »), (s1 , a))
((b, s1 , »), (s1 , b))
((a, s1 , »), (s2 , »))
((a, s2 , a), (s2 , »))
((b, s2 , b), (s j , »))
(a) Complete the statements in the table.
(b) Construct the ¬‚ow chart for the PDA.
(14) Given a pushdown automaton M = ( , S, s0 , I, ’, F) where = I =
{a, b}, Q = {s0 , s1 , s2 }, F = {s2 }, and ’ has the following relations:
((a, s0 , »), (s1 , a)) In state s0 , a is read, go to state s1 and push a
((b, s0 , »), (s1 , b))
((a, s1 , a), (s1 , b))
((a, s1 , b), (s1 , b))
((a, s1 , a), (s2 , a))
((b, s1 , a), (s j , »))
((a, s2 , a), (s2 , a))
((b, s2 , a), (s j , »))
Automata
98


(a) Complete the statements in the table.
(b) Construct the ¬‚ow chart for the PDA.
Let = {a, b, c}. Construct a pushdown automaton that reads the lan-
(15)
guage L = {wcwr : w ∈ {a, b}— }.
Let = {a, b, c}. Construct a pushdown automaton that reads the lan-
(16)
guage L = {a n cbn : n is a nonnegative integer}.
Let = {a, b, c}. Construct a pushdown automaton that reads the lan-
(17)
guage L = {wwr : w ∈ {a, b}— }.
Let = {a, b, c}. Construct a pushdown automaton that reads the lan-
(18)
guage L = {wcwr : w ∈ {a, b}— }.
Let = {a, b, c}. Construct a pushdown automaton that reads the lan-
(19)
guage L = {w : The number of as in w is equal to the sum of the number
of bs and cs}.
Let = {a, b}. Construct a pushdown automaton that reads the language
(20)
L = {w : The number of as in w is equal to twice the number of bs or the
number of bs in w is equal to three times the number of as}.
(21) Given two pushdown automata
= (N , ’, S, P)
and
= (N , ’ , S , P )
over the same alphabet and accepting languages L and L respectively,
(a) Describe how to construct a pushdown automaton 1 that accepts the
language L ∪ L .
(b) Construct a pushdown automaton 1 that accepts the language L ∪ L
where L is the language accepted by the automaton in Example 3.26
and L is the language accepted by the automaton in Example 3.27.
(22) Given two pushdown automata
= (N , ’, S, P)
and
= (N , ’ , S , P )
over the same alphabet and accepting languages L and L respectively,
(a) Describe how to construct a pushdown automaton 2 that accepts the
language L L .
(b) Construct a pushdown automaton 2 that accepts the language L L
where L is the language accepted by the automaton in Example 3.26
and L is the language accepted by the automaton in Example 3.27.
3.7 Mealy and Moore machines 99


(23) Given a pushdown automaton = (N , ’, S, P) over the alphabet and
accepting language L,
(a) Describe how to construct a pushdown automaton 3 which accepts
the language L — .
(b) Construct a pushdown automaton 3 that accepts the language L ∪ L
where L is the language accepted by the automaton in Example 3.26
and L is the language accepted by the automaton in Example 3.27.
(24) Given two pushdown automata
= (N , ’, S, P)
and
= (N , ’ , S , P )
over the same alphabet and accepting languages L and L respectively,
Construct a pushdown automaton 4 that accepts the language L ∪ L
where L is the language accepted by the automaton in Example 3.26 and
L is the language accepted by the automaton in Example 3.27.



3.7 Mealy and Moore machines
Previously, we de¬ned a deterministic automaton, a device which only accepts
or recognizes words of a language of — . We now produce two machines which
are similar to deterministic automata, but produce output.
The ¬rst machine we introduce is called a Moore machine, created by E. F.
Moore[30] and is denoted by ( , A, S, s0 , ’, φ). It also has a ¬nite set of states
S including a starting state s0 . It contains two alphabets and A. The ¬rst is
the alphabet of input characters to be read by the machine. The second is the
alphabet of output characters produced by the machine. The Moore machine
retains the transition function ’ : S — ’ S of the ¬nite state automaton.
It also contains an output function φ : S ’ A. In the operation of a Moore
machine, the output is ¬rst produced using the output function φ before the
transition function F is used to read the input and change states. Imitating the
deterministic automaton, the Moore machine reads each element of a string w of
characters of until it has read the entire string. During this process, it produces
output consisting of a string of characters of A. Since the Moore machine
produces output φ(s0 ) before the ¬rst input character is read and produces
output from the last state reached before the transition function tries and fails to
read input, the output string contains one more character than the input string.
Also since φ(s0 ) is always executed ¬rst, each output string must begin with
Automata
100


φ(s0 ). As with the deterministic automata, we say a Moore machine reads a
symbol a of the alphabet to indicate that the letter a is used as input for the
function ’. Similarly, in state si , if the output is φ(si ), we shall say that the
machine prints the value φ(si ), although the output may be used for an entirely
different purpose. Thus one may envision a Moore machine reading a string in
from a tape and printing a string in A— on the tape or on another tape.
As with the ¬nite state automaton, we shall illustrate the Moore machine
using a ¬nite state diagram. As in the deterministic automaton, if ’(si , a) = s j ,
this is represented by

sj
a
si


If φ(si ) = z, this is represented by

si /z


so that both si and φ(si ) are represented inside the vertices of the diagram.
In the diagram

a a
b b s2
s1
s0
0 0
1
a
b

= {a, b}, A = {0, 1}, S = {s0 , s1 , s2 }, ’ is given by the table

F s0 s1 s2
a s0 s0 s2
b s1 s1 s2

and φ is given by the table

φ(s)
s
s0 1
s1 0
s2 0
3.7 Mealy and Moore machines 101


Given the input string aba, the machine ¬rst prints the value φ(s0 ) = 1. It
then reads a and remains in state ’(a, s0 ) = s0 . It then prints φ(s0 ) = 1. Next
it reads b and travels to state ’(b, s0 ) = s1 . It then prints φ(s1 ) = 0. Next it
reads a and travels to state ’(a, s1 ) = s0 . It then prints φ(s0 ) = 1. Since there
is no more input, operations cease. The result is the output string 1101. The
input string aabab produces the output string 111010. The input string baab
produces the output string 10110.
Note that the Moore machine we have produced is actually the ¬nite
automaton


a a
b b s2
s1
s0
0 0
1
a
b


except that we have added φ with the property that φ(si ) = 0 if si is not an
acceptance state and φ(si ) = 1 if si is an acceptance state. When we do this,
the last character printed will be 1 if and only if the input is accepted by the
¬nite automaton. Thus since the outputs for aba and ababa are 1101 and
110101 respectively, aba and ababa are accepted by the automaton. Using
this procedure we can “duplicate” any ¬nite automaton with a Moore machine
where a word is accepted only if the last character output is 1. It may also be
observed that whenever a 1 appears in the output, the initial string of input which
has been read at that point is accepted by the ¬nite automaton since the state
at that point is an acceptance state. For example, in the above example input
aabaabbab produces output 0001001001, so aab, aabaab, and aabaabbab
are all accepted by the automaton. Since φ(s0 ) = 1 the empty word is also
accepted. In general, the number of 1s in the output of a Moore machine which
“duplicates” a ¬nite automaton is the number of initial strings of the input which
are accepted by the ¬nite automaton.

Example 3.28 The automaton


b
a a
a
b
s0 s1 s2 a s3
b
b
Automata
102


has corresponding Moore machine

b
a a,b
a
a
b
s1 /0 s2 /1 s3 /0
s0 /0

b

Input babbab produces output 0010010 so substrings ba and babba are
accepted by the automaton. Since the input ababbbaa produces output
000100000, the only substring accepted by the automaton is aba since only
one 1 occurs.
Example 3.29 A unit delay machine delays the appearance of a bit in a string
by one bit. Hence the appearance of a character in the output is preceded by
one character in the input. The following machine is a unit delay machine.

s1 /0
0

s0 /0 1 0

1 s2 /1



So far, we have primarily shown that a Moore machine may be used to
“duplicate” a ¬nite automaton. This is only one of the uses of a Moore machine.
However, any task performed by a Moore machine can be performed by another
machine called a Mealy machine and conversely. In most cases the task is more
easily shown using a Mealy machine.
The Mealy machine also contains an output function, however, the input is
an edge rather that a state. Since the edge depends on the state and the input,
the output function δ “reads” a letter of a ∈ and the current state and prints
out a character of the output alphabet. Hence δ is a function from S — to A.
More formally a Mealy machine is a sextuple Me = ( , A, S, s0 , ’, δ) where
, A, S, s0 , and ’ are the same as in the Moore machine and δ : S — A ’ .
The Mealy machine is also best illustrated using a ¬nite state diagram. Since
δ depends on both the state and the letter read, we shall denote the output by
placing it on the edge so that

a/z
sj
si
3.7 Mealy and Moore machines 103


corresponds to ’(si , a) = s j and δ(si , a) = z. Note that, unlike in the Moore
machine, the output occurs after the input is read. Hence for every letter of
input, there is a character of output.
Consider the Mealy machine

a /1

b/0 s1
s0

a/1
b /0
b/0
s2

a/0

The functions ’ and δ are given by tables

’ s0 s1 s2
a s1 s2 s2
b s2 s0 s1

and

δ s0 s1 s2
a 1 1 0
b 0 0 0

Given the input string aaabb, a is read, 1 is printed, and the machine moves to
state s1 . The second a is read, 1 is printed, and the machine moves to state s2 .
The third a is read, 0 is printed, and the machine remains at state s2 . The letter
b is read, 0 is printed, and the machine moves to state s1 . Finally, b is read, 0
is printed, and the machine reaches state s0 . Thus input aaabb produces output
11000.
Example 3.30 The Mealy machine

a/x
b/y
s0
c/z


simply converts every a in the string to x, every b to y, and every c to z. Thus
aabbcca is converted to x x yyzzx.
Automata
104


Example 3.31 The 1s complement of a binary string converts each 1 in the
string to a 0 and each 0 to a 1. It is given by the state diagram

s0 0/1
1/0


Example 3.32 If 1 is added to the 1s complement of a binary string of length
n, we obtain the 2s complement used to express the negative of an integer
if we discard any number carried over beyond n digits. Thus 1111 + 1 =
0000.
The following Mealy machine adds 1 to a binary string in this fashion. The
input string must be read in backwards and the output is printed out backwards
so the unit digit is read ¬rst. The stage diagram

0/0


0/1
s0 s1


1/0 1/1

describes the Mealy machine. In this diagram, s1 is the state reached if there is
no 1 to carry when adding the digits. The state s2 is reached if there is a 1 to
carry when adding the digits. Let 1101 be the number in reverse. (Hence the
actual number is 1011.) First input 1 is read. The output is 0 and the machine
is in state s2 . (This corresponds to 1 + 1 = 10 so 0 is output and 1 is carried.)
Now input 1 is read. The output is 0 and the machine remains in state s2 .
(This corresponds to 1 + 1 = 10 so 0 is output and 1 is carried.) Next 0 is
input. The output is 1 and the machine moves to state s1 . (This corresponds to
1 + 0 = 1 so 1 is output and nothing is carried.) Finally 1 is input. The output
is 1 and the machine remains in state s1 . (This corresponds to 1 + 0 = 1 so
1 is output and nothing is carried.) Thus the output is 0011 and the number
is 1100.
Example 3.33 The Mealy machine M+ adds two signed integers. The signed
integer m is subtracted from the signed integer n by adding n to the 2s com-
plement of m. Thus M+ can also be used for subtraction by ¬rst using the
machine in the previous example to ¬nd the 2s complement of the number to
be subtracted. Assume an , an’1 , . . . , a2 , a1 and bn , bn’1 , . . . , b2 , b1 are the two
strings to be added. We again assume that the two strings to be added are read
3.7 Mealy and Moore machines 105


in reverse so the ¬rst two digits to be input are a1 and b1 , followed by a2 and
b2 , . . . , followed by an and bn . We shall consider the pair of digits to be input
as ordered pairs, so that (a1 , b1 ) is the ¬rst element of input. The machine M+
is

(0,0)/0 (0,1)/0

(1,1)/0 (1,0)/0
s1
s0
(0,0)/1
(0,1)/1
(1,0)/1 (1,1)/1


The machine is in state s0 when no 1 has been carried in adding the previous
input and is in state s1 when a 1 has been carried in the addition. Assume that
0101 and 1101 are added. First (1, 1) is read, so the machine moves to s1 and
prints 0. Next (0, 0) is read, so the machine moves to s0 and prints 1. Then (1, 1)
is read, so the machine returns to s1 and prints 0. Finally (1, 0) is read, so the
machine remains at s1 and prints 0. Note that the 1, if it exists, which is carried
from adding the last two digits is discarded. Thus the sum of 0101 and 1101 is
0010.

Earlier in this section, we implied that Moore machines and Mealy machines
were equivalent in the sense that every Moore machine could be duplicated by
a Mealy machine and conversely. More speci¬cally, given a Moore machine,
there is a Mealy machine which will produce output equivalent to the Moore
machine when given the same input. Conversely given a Mealy machine, there
is a Moore machine which will produce the output equivalent to the Mealy
machine when given the same input.
We ¬rst need to specify what we mean by equivalent output since a Mealy
machine always has one less symbol of output than the Moore machine. A
string of output of a Mealy machine is equivalent to a string of output of a
Moore machine if it is equal to the substring of the Moore machine excluding
the ¬rst symbol φ(s0 ). Thus if the Moore machine produced output 010010101,
the equivalent output from the Mealy machine would be 10010101.
The transformation from the Moore machine to an equivalent Mealy machine
is the simplest. With the transition

c
s1/a1
s0 /a0
Automata
106


in a Moore machine, given input c, the character a0 will be printed, the machine
will move to state s1 , and a1 will next be printed. In the transition

c/a1
s1
s0


of a Mealy machine, the machine will move to state s1 with input c and a1 will
be printed. Since we disregard a0 in the string produced by the Moore machine
in our de¬nition of equivalent output, we have begun with the same output.
Assume that we have the transition
b
sj /aj
si /ai


in a Moore machine and ai has already been printed. Input b moves the machine
to state s j , and the next output will be a j . The corresponding transition in the
Mealy machine is

b/aj
sj
si


which produces the same transition and output.
Example 3.34 The Mealy machine corresponding to the Moore machine

a b
b



s1 /0 b
s0 /1 a s2 /0


a

is
a /0 b/0
b/1


a/0 b/0
s1 s2
s0


a /1
3.7 Mealy and Moore machines 107


In transforming a Mealy machine to a Moore machine, we have to consider
the problem where arrows into a given state produce different output. Consider
the following example:

a/ x c/z
s
b/y

In a Moore machine, the state s produces unique output so it cannot produce
both x and y as output. We solve this by making two copies of s

a c /z
s x/x


s y/ y c/z
b

One will produce x as output and the other y as output as follows. Obviously
both machines produce output x with input a and output y with input b. For
simplicity, we shall simplify s x /x to s/x and s y /y to s/y noting that they are
different states.
In general, for each state s, except the starting state, in a Mealy machine and
for each output symbol z, we shall produce a copy s/z of the state s. This may
result in some overkill since in the above example, if the output symbols were x,
y, and z, we would not have needed state s/z since there was no arrow entering
s with output z. We begin with initial state s0 and give it an arbitrary output
variable x0 from the set of output variables since it is not used in producing
output equivalent to the Mealy machine. If we have

a/ x
b/ y
s0 si
c/z
¦




in the Mealy machine, we replace it with

a si / x

b
s0 / x0 si / y

c
¦




si / z
Automata
108


in the Moore machine. For other states, we replace
b/y
a/ x
si sj


with
a b
sj /y
si /x


We produce the same output at each step for both machines.
Thus the machine equivalent to
b/0
s1
a/1
a/0
s3
a/1
s0 b/0 b/1
s2 a/1
b/0

is strcj.eps

s1/0 b
b
a
s0 /0
b
s3 /0 a
s1/1
b
a
b a b
a
s2 /0
b
s3 /1
a
a
s2 /1




Exercises
(1) Let the Moore machine Mo = ( , A, S, s0 , ’, φ) be given by the
diagram

b
a a,b
a
a
b
s1 /0 s2 /1 s3 /0
s0 /0

b

, and S. Find tables for F and φ.
Describe A,
3.7 Mealy and Moore machines 109


(2) Let the Moore machine Mo = ( , A, S, s0 , ’, φ) be given by the
diagram

a
s0 /0 s1 /1
b c
a
c
b
a c
b
b
s2 /1 s3 /0
a
c

Describe A, , and S. Find tables for ’ and φ.
(3) Let the Moore machine Mo = ( , A, S, s0 , ’, φ) be given by the
diagram

b
s1 /0
b
a
a
s0 /1
a
b s3 /1
a b
s2 /1


(a) Find the output with input bbabab.
(b) Find the output with input aaabbaba.
(c) Find the output with input bbbaaa.
(d) Find the output with input », the empty word.
(4) Let the Moore machine Mo = ( , A, S, s0 , ’, φ) be given by the
diagram

a
s0 /0 s1 /1
b c
a
c
b
a c
b
b
s2 /1 s3 /0
a
c

Find the output with input abcabca.
(a)
Find the output with input bbbaaacc.
(b)
Find the output with input aabbccaa.
(c)
Find the output with input », the empty word.
(d)
Automata
110


(5) Find the Moore machine that duplicates the ¬nite automaton

a a,b

a
b b
s0 s1 s2 s3
b
a


(6) Find the Moore machine that duplicates the ¬nite automaton

<<

. 4
( 9)



>>