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