for a ∈ in ’ include the rule

If in state s0 and a is read, go to state s j

in ’ .

Example 3.16 Let M be the automaton

a

a a b

s2

s1

s0 b b

and M be the automaton

a a,b

a

s'2

s'1

s'0 b b

b

Automata

58

Using the above procedure we have the automaton M which accepts the union

of M(L) and M (L) given by

a

a,b

a a b

s2

s1

s0 b b

s"

0

a a a,b

s'2

s'1

s'0 b b

a,b

b

Example 3.17 Let M be the automaton

a a,b

a

b b

s0 s1 s2 s3

b

a

and M be the automaton

a

s1

a

s0 b

b

b s2

a

Using the above procedure we have the automaton M which accepts the union

of M1 (L) and M1 (L)

a,b

a

b

a

b b

s0 s1 s3

s2

b

a a

a a

s"

0

s'1

a

s'0 b

b

b

s'2

b

a

3.2 Kleene™s Theorem 59

An alternative method for ¬nding the union of two automata is now given.

If Q is the set of states for M and Q is the set of states for M , let Q — Q =

{(si , s j ) : si ∈ Q, s j ∈ Q } be the set of states for M. If there is an ai -arrow from

si to sk in M and an ai -arrow from sl to sm in M , then construct an ai -arrow

from (si , sl ) to (sk , sm ). In this way, we read the same letter simultaneously

in M and M . Since a word is accepted if it is accepted by either M or M ,

if si is a terminal state in M or s j is a terminal state in M , then we want

(si , s j ) to be a terminal state in M . Therefore if F is the set of terminal states

of M and F is the set of terminal states of M , the set of terminal states for

M is Q — F ∪ F — Q . We require that both M and M be deterministic

since we do not want M to “hang” in one automaton before being accepted

in the other. This is no restriction since we have shown that any language

accepted by a nondeterministic automaton is also accepted by a deterministic

automaton.

Example 3.18 Let M be the automaton

a

a a b

s2

s1

s0 b b

and M be the automaton

a a,b

a

s'2

s'1

s'0 b b

b

It may be that all of the states in Q 1 — Q 1 are not needed. We begin with (s0 , s0 )

as the start state. Since there is an a-arrow from s0 to s1 and an a-arrow from

s0 to s1 , we construct an a-arrow from (s0 , s0 ) to (s1 , s1 ). Since there is also a

b-arrow from s0 to s1 and a b-arrow from s0 to s1 , we construct a b-arrow from

(s0 , s0 ) to (s1 , s1 ). Since there is an a-arrow from s1 to s1 and an a-arrow from s1

to s2 , we construct an a-arrow from (s1 , s1 ) to (s1 , s2 ). There is a b-arrow from

s1 to s2 and a b-arrow from s1 to s2 , so we construct a b-arrow from (s1 , s1 ) to

(s2 , s2 ). Continuing at (s1 , s2 ), there is an a-arrow from s1 to s1 and an a-arrow

from s2 to s2 , we construct an a-arrow from (s1 , s2 ) to (s1 , s2 ). There is a b-

arrow from s1 to s2 and a b-arrow from s2 to s2 , so we construct a b-arrow from

(s1 , s2 ) to (s2 , s2 ). Continuing at (s2 , s1 ), there is an a-arrow from s2 to s1 and

an a-arrow from s1 to s2 , so we construct an a-arrow from (s2 , s1 ) to (s1 , s2 ).

Automata

60

There is a b-arrow from s2 to s2 and a b-arrow from s1 to s2 , so we construct

a b-arrow from (s2 , s1 ) to (s2 , s2 ). Finally, consider state (s2 , s2 ). There is an

a-arrow from s2 to s1 and an a-arrow from s2 to s2 , so we construct an a-arrow

from (s2 , s2 ) to (s1 , s2 ). There is a b-arrow from s2 to s2 and a b-arrow from s2

to s2 , so we construct a b-arrow from (s2 , s2 ) to (s2 , s2 ). The terminal states are

(s1 , s2 ), (s2 , s1 ), and (s2 , s2 ). Thus M is the automaton

a

a

b

(s1 ,s'2)

a

b

(s0 ,s'0) (s1 ,s'1)

a

( s2 ,s'2 )

a

b

b

(s2 ,s'1)

b

Note that aabb is accepted by M. In M , reading aabb takes us from state

(s0 , s0 ) to state (s1 , s1 ) to state (s1 , s2 ) to state (s2 , s2 ) to state (s2 , s2 ). Since

(s2 , s2 ) is a ¬nal state in M , M accepts aabb. Note also that aba is accepted

by M . In M , reading aba takes us from state (s0 , s0 ) to state (s1 , s1 ) to state

(s2 , s1 ) to state (s1 , s2 ). Since (s1 , s2 ) is a terminal state in M , M accepts

aba.

Let M1 be the automaton

Example 3.19

a

s1 b

s3

a

aa

b

s0 s2

b

b

and M1 be the automaton

a,b

a a

s'2

s'0 s'1

b b

3.2 Kleene™s Theorem 61

Using the same process as in the previous example, we ¬nd that M is the

automaton

b

(s3 ,s'0)

(s0 ,s'0) a

(s1 ,s'1)

a

b b

a

(s2 ,s'2) (s3 ,s'1) b

a

b a

(s2 ,s'0)

b b

(s2 ,s'1) (s3 ,s'2)

a

b

a

We have now shown that every operation in a regular language can be dupli-

cated by an automaton. Hence we have the following lemma.

Lemma 3.3 For every regular language L, there exists an automaton M so

that L is the language accepted by M.

The formal proof that a language accepted by an automaton is regular gives

no procedure for actually converting an automaton to a language accepted by an

automaton. Before giving a proof that the language accepted by an automaton

M is regular, we ¬rst give some examples where, given a certain automaton, we

can construct the language accepted by this automaton. This is not part of the

proof but only an illustration. To perform this construction, we use transition

graphs. These are merely ¬nite state machines which read strings of a regu-

lar expression rather than elements of to change states. One of the regular

expressions we shall use is the empty word » so that one may change states

reading the empty word which is equivalent to changing states without read-

ing anything. The form of the transition graph will become obvious as we use

them.

The process for constructing the regular expression is to ¬rst have only one

initial and one terminal state. We then eliminate one state at a time from the

state diagram and resulting transition graphs and in each case get a transition

graph with e-arrows between states, where e is a regular expression. Eventually

Automata

62

we get a transition graph of the form

e1

e2

s0 T

¦

en

which accepts the expression e1 ∨ e2 ∨ e3 ∨ · · · ∨ en .

If there is more than one terminal state, say there are terminal states

t1 , t2 , t3 , . . . , tm , then replace the states

¦ t1

¦ t2

¦ t3

¦ t4

with

¦ t1 l

l

¦ t2

T

¦ l

t3

l

¦ t4

Note that this new diagram accepts the same language as M.

To eliminate the state si we use the following rules.

(1) If the diagram

a,b,c

si

3.2 Kleene™s Theorem 63

occurs, replace it with

(a∨b∨c)*

si

More generally if the diagram

e1,e2,...ek

si

occurs, where e1 ,e2 ,e3 , · · · , ek are regular expressions, then replace it with

the diagram

(e1∨e2∨e3∨...∨ek)

si

(2) If the diagram

b

si’1 a c si+1

si

occurs, then replace it with the diagram

*

si ’1 ab c si +1

More generally if the diagram

e2

e1 e3

si ’1 si+1

si

occurs, where e1 ,e2 ,e3 are regular expressions, then replace it with the

diagram

e1e2*e3

si ’1 si +1

In particular, when e2 = », then e1 e— e3 becomes e1 e3 so that the diagram

2

a b

si’1 si+1

si

Automata

64

is replaced by the diagram

ab

si’1 si+1

(3) If the diagram

a

b

w si +1

si

c

occurs, then replace it with the diagram

w a∨b∨c

si si+1

More generally if the diagram

e1

e2

si+1

si

¦

ek

occurs, where e1 ,e2 ,e3 , · · · ,ek are regular expressions, then replace it with

the diagram

e1∨e2∨¦∨ek

si si+1

(4) If the diagram

a

c

s2 si+1

si’1 b

occurs, then replace it with the diagram

a(ba)*c

si+1

si’1

More generally if the diagram

e1

e3

s2 si+1

e2

si ’1

3.2 Kleene™s Theorem 65

occurs, where e1 ,e2 ,e3 are regular expressions, then replace it with the

diagram

e1(e2e1 )*e3

si+1

si ’1

(5) If the diagram

si+1

b

a

si ’1 si c

si+2

occurs, then replace it with the diagram

si+1

ab

sk’1

ac

si+2

More generally if the diagram

si+1

e1

e2 si+2

e si

sk’1 e3

si+3

en

¦

si+4

occurs, where e,e1 ,e2 ,e3 , · · · ,ek are regular expressions, then replace it

with the diagram

ee1 si+1

ee2 si+2

sk’1 ee3

si+3

¦

eew

si+n

Automata

66

Example 3.20 Assume we begin with automaton

b

b

s2 s3

a

a

s0 s1

b

a s5

s4

a

We then add a new terminal state T to get the automaton

b

b

s2 s3

a l

a

s0 s1

T

b

l

a

s4 s5

a

We now apply rule (2) to get the automaton

b

ab

a

s0 s1 T

ba*a

Apply rules (2) and (3) to get the automaton

ab*ab

s0 T

ab*ba*a

Hence the regular expression is ab— ab ∨ ab— ba— a.

Example 3.21 Given the automaton

a

b

s1 s4

a

s0 b

b

a s5

s3

3.2 Kleene™s Theorem 67

we go through the following steps

a

b

s1 s4 l

a

s0 b T

l

a

b s3 s5

a

b

s1 s4 l

a

s0 T

l

a

aa *b s3 s5

∨ b

aa*b

s0 T

(aa*b∨b)a

to get the regular expression ((aa— b ∨ b)a) ∨ aa— b).

Example 3.22 Given the automaton

a,b

s2

a

a

s0 s1

b

b

s3

we go through the following steps,

a,b

s2 l

a

a

s0 s1 T

b b l

s3

(a∨b)*

a

a∨b

s0 s1 T

b

(a∨b)*

a∨b

a∨b

s0 s1 T

Automata

68

to get the regular expression (a ∨ b)(a ∨ b)— (a ∨ b). Note that the process is not

unique and that by taking different steps, we would have had a different, but

equivalent, regular expression. Thus both expressions would have described the

same set.

We now give a formal proof of the following lemma

The language accepted by an automaton is regular.

Lemma 3.4

Proof Given a ¬nite deterministic automaton M = ( , Q, s0 , ’, F) we wish

to show that L = L(M), the language accepted by the automata, is regular.

To do this we will express L as the union of a ¬nite number of regular lan-

guages, and since the union of regular languages is regular, L is regular. Let Q

contain n elements q1 , q2 , . . . , qn , where s0 = q1 . For i, j = 1 to n and k = 1

to n + 1, let R(i, k, j) be the set of all words w such that (qi , w) — (q j , »)

without passing through any qm where m ≥ k. However, qi and q j do not

have this restriction. Thus there is a path in the automata such that M in

state qi reads w and is then in q j without passing through m where m ≥ k.

Thus if (qi , w) — (qm , w ) — (q j , ») then m < k or m = i and w = w or

m = j and w = ». Hence the restriction is only on interior states of the path.

Since there are only n states, R(i, n + 1, j) = {w : (qi , w) — (q j , »). Hence

L = ∪{R(i, m, j) : j ∈ Q.

To complete the proof, we need to show that R(i, p, j) is regular for 1 ¤ p ¤

n + 1. We do this using induction. If p = 1, then there are no interior states in

the path so R(i, p, j) = {a ∈ : δ(qi , a) = q j } if i = j and {»} ∪ {a ∈ :

δ(qi , a) = q j } if i = j. Hence we have a ¬nite set of elements of and possibly

» in the set so it is a regular set.

Assume R(i, k, j) is regular. The set of words R(i, k + 1, j) can be de¬ned

as

R(i, k + 1, j) = R(i, k, j) ∪ R(i, k, k)R(k, k, k)— R(k, k, j)

where the path from qi to q j may not pass through a state qm where m ≥ k or

that passes along a path from qi to qk , then passes through zero or more paths

from qk to qk and ¬nally passes along a path from qk to q j . None of these paths

passes along an interior state qm where m ≥ k. Since R(i, k + 1, j) is formed

using union, concatenation, and Kleene star of regular states, it is regular and

hence L is regular.

Since we have now shown that every regular expression is accepted by an

automaton and that the language accepted by an automaton is regular, we have

proven Kleene™s Theorem.

3.2 Kleene™s Theorem 69

As a result of Kleene™s Theorem, we discover two new properties about the

regular languages:

Theorem 3.4 If L 1 and L 2 are regular languages, then

— —

’ L 1 = {x : x ∈ and x ∈ L 1 }

/

and L 1 © L 2 are regular languages.

Proof To show — ’ L 1 is regular, let M1 be a deterministic automaton for

L 1 . To construct the automaton for — ’ L 1 , simply change all of the terminal

states in M1 to nonterminal states and all of the nonterminal states to terminal

states. As a result, all words that were accepted because the automaton stopped

in a terminal state, are no longer accepted and all words which were not accepted

are now accepted since the automaton will now stop in a terminal state after

reading this word.

To show that L 1 © L 2 is a regular language we simply use the set theory

property that

— — —

L1 © L2 = ’ (( ’ L 1) ∪ ( ’ L 2 )).

This is most easily seen by thinking of — as the universe so that — ’ L 1 = L 1

and the statement is simply L 1 © L 2 = (L 1 ∪ L 2 ) which follows immediately

from De Morgan™s law and the fact that L = L . Since the set of regular lan-

guages is closed under union and complement (¬rst part of theorem), it is closed

under intersection.

Exercises

(1) Let L 1 be the language accepted by the automaton

a

a a b

s2

s1

s0 b b

and L 2 be the language accepted by the automaton

a a,b

a

s'2

s'1

s'0 b b

b

(a) Construct the automaton which accepts the language L 1 ∪ L 2 .

Automata

70

(b) Construct the automaton which accepts the language L 1 L 2 .

(c) Construct the automaton which accepts the languages L — and the

1

automaton which accepts L — .

2

(2) Let L 1 be the language accepted by the automaton

a

s1 b

s3

a

aa

b

s0 s2

b

b

and L 2 be the language accepted by the automaton

a,b

a a

s'2

s'0 s'1

b b

(a) Construct the automaton which accepts the language L 1 ∪ L 2 .

(b) Construct the automaton which accepts the language L 1 L 2 .

(c) Construct the automaton which accepts the languages L — and the

1

—

automaton which accepts L 2 .

(3) Let L 1 be the language accepted by the automaton

b

s3

s1

a a

s0 b

b

s4

s2

b

a

and L 2 be the language accepted by the automaton

b

b b

s1 s2

a a

s0 b

b

s3 s4

b

b

a

3.2 Kleene™s Theorem 71

(a) Construct the automaton which accepts the language L 1 ∪ L 2 .

(b) Construct the automaton which accepts the language L 1 L 2 .

(c) Construct the automaton which accepts the languages L — and the

1

—

automaton which accepts L 2 .

(4) Let L 1 be the language accepted by the automaton

b

s1

b

a

a s3

b

s0

b

s2 a

a

and L 2 be the language accepted by the automaton

a a

b s3

s1

a

s0 a b

b b

b

s2 s4

a

(a) Construct the automaton which accepts the language L 1 ∪ L 2 .

(b) Construct the automaton which accepts the language L 1 L 2 .

(c) Construct the automaton which accepts the languages L — and the

1

—

automaton which accepts L 2 .

(5) Using transition graphs, construct the regular language accepted by the

automaton.

a

a

s0 s3

s1

b

a a,b

b

b

s4

Automata

72

(6) Using transition graphs, construct the regular language accepted by the

automaton.

b

a,b

a

a s4

s1 s2

a

b a

s0 a

b b b s6

s3 s5

a,b

s7

a,b

(7) Using transition graphs, construct the regular language accepted by the

automaton

a

a

a

s0 s3

s1

a b

b

s2

(8) Using transition graphs, construct the regular language accepted by the

automaton

b

a

b s1 s2

a

b

s0 a b

s5 a

b s3

a

b

a

s4

3.3 Minimal deterministic automata and

syntactic monoids

In this section, we discuss minimal automata and the transformation monoid.

We then show how they can be combined to produce the syntactic monoid

of a language. We begin with the de¬nition of an accessible deterministic

automaton:

3.3 MDAs and syntactic monoids 73

De¬nition 3.3 The state s of an automaton M is accessible if there exists a

word w in — so that if M reads the word w, it is then in state s. Equivalently

the state s of an automaton M is accessible if there exists a word w in — so

that in reading w, M passes through state s. An automaton M is accessible if

every state in the automaton M is accessible.

Intuitively a state s is accessible if one can begin at s0 and follow a path of

arrows to reach the state s.

For the moment, we shall adopt the following de¬nition of a minimal automa-

ton with a ¬nite number of states.

De¬nition 3.4 A deterministic automaton M is a minimal if the number of

states in M is less than or equal to the number of states in any other deterministic

automaton accepting the same language as M.

Assume ’ is not empty. Obviously, if a state s in an automaton M is not

accessible, it can be removed without changing the language accepted by M,

but is M still deterministic? The answer is yes, if all of the states which are

not accessible are removed. The reason is that if there is an a-arrow from s to

s and s is not accessible, then s is not accessible, since any path from s0 to s

could be extended to a path from s0 to s .

An alternative way to deterine which states are accessible is to begin at the

initial state s0 and list all states to which there is an arrow from s0 . Call this list

X . Enlarge X by adding any state to which there is an arrow from some state

already in X . Iterate until X is no longer enlarged. The list X is then the set of

accessible states.

A state h is co-accessible to a state g if there is no word of arrows from

h to g. To ¬nd the co-accessible states, reverse the arrows and begin with the

acceptance states.

A minimal state has no states that are not accessible or co-accessible. So

they may be removed.

Therefore the ¬rst step in constructing a minimal deterministic automaton is

to remove all states which are not accessible or co-accessible. Hence a minimal

automaton is accessible and co-accessible.

We will now give an algorithm for constructing the minimal automaton which

accepts a given language. The ¬rst begins with an automaton for the language

and constructs the minimal automaton. The second begins with an automaton

accepting the language and uses it to construct the minimal automaton.

At this point, we have several problems. The ¬rst is that removing states that

are not accessable or not co-assessible does not necessarily give us a minimal

automaton so we need to ¬nd out how to ¬nd a minimal automaton. (It does

Automata

74

however tell us if the language is empty or consists only of the empty word.)

The second is, for a given language, whether the minimal automaton is unique,

even up to isomorphism.

At this point we will develop a method for developing a minimal automaton

which has two advantages. It is developed using the language, so if we use this

proceedure, and de¬ne a minimal automaton to be the one developed by this

procedure, we will be able to consider the minimal automaton. The second

advantage is that the procedure works for all languages although we already

know that the automaton will have a ¬nite number of states if and only if the

language is regular.

In addition we shall develop a monoid called the syntactic monoid which

will be discussed later (see Theorem 3.7). We introduce it now because the

development of the minimal automaton and syntactic monoid are interrelated.

We now develop and de¬ne the intrinsic automaton and the syntactic

monoid of an arbitrary language.

De¬nition 3.5 As usual: is the alphabet; — is the set of all strings over

and L is a language over , i.e., a subset of — . Relative to the language

L we de¬ne the intrinsic (or minimal) automaton M of L: The “states” of

M are the equivalence classes de¬ned, for each x ∈ — , by [x] = {y ∈ — |

R(y) = R(x)}, where R(x) is the set of “right contexts” accepted by x relative

to L. Speci¬cally: R(x) = {v ∈ — | xv ∈ L}. Each symbol a in “acts on”

the state [x] by [x]a = [xa] where xa = ’(x, a). M has a speci¬ed Start state,

1, and a speci¬ed set of Acceptance states, {[x]|x ∈ L}. We may view M as

a directed arrow-labeled graph having the states of L as its vertices, having

directed edges ([x], a,[xa]) where the second term is in and is called the

label of the arrow. The automaton M is considered to “recognize” each string

in — , which produces a path from a Start state to an Acceptance state.

The constructed M recognizes precisely those strings that are in L. A lan-

guage L is regular if its automaton has only ¬nitely many states. Since for each

word in the language, there is a unique path from the start state to an acceptance

state, the intrinsic automaton is minimal with regard to the above de¬nition.

De¬nition 3.6 The syntactic monoid S of L has as its elements the equiva-

lence classes de¬ned, for each x ∈ — , by [[x]] = {y ∈ — | L R(y) = L R(x)},

where L R(x) is the set of “two-sided contexts” accepted by x relative to the

language L. Speci¬cally, L R(x) = {(u, v) ∈ — — — | uxv ∈ L} and S has

an associative binary operation that is “well de¬ned” by setting [[x]][[y]] =

[[x y]].

3.3 MDAs and syntactic monoids 75

Since [[1]] serves as a two-sided identity for this operation, S has the structure

of a monoid, i.e., semigroup with an identity element. The partition of — into the

classes [[x]] re¬nes the partition of — into the classes [x] since L R(x) = L R(y)

implies R(x) = R(y). Consequently when S is ¬nite L is regular.

The action of on the states of L extends, inductively, to an action of —

on the states of L. Consequently each string y ∈ — determines a function

from the state set of L into itself de¬ned by [u]x = [ux]. Two strings x and y

determine the same function precisely if, for every u ∈ — , [ux] = [uy]. But

this holds precisely if, for all v ∈ — , uxv ∈ L if and only if uyv ∈ L. Thus x

and y determine the same function precisely if [[x]] = [[y]]. When L is regular

there can be only a ¬nite number of functions from the state set of L into itself.

Consequently when L is regular S is ¬nite.

Summary For every language L we have an intrinsically associated automa-

ton that recognizes the language and we have an associated syntactic monoid.

The following are equivalent: (1) L is a regular language; (2) the intrinsic

automaton for L has only ¬nitely many states; and (3) the syntactic monoid of

L is ¬nite.

The word “intrinsic” is used because each language provides a unique

automaton using this process (not just an isomorphism type “ but one unique

set of states, and arrows (or transitions). Thus if it is used there is no concern

about isomorphism “ the intrinsic automaton is 100% unique.

Now the question of isomorphism can come up (as it certainly will in

elementary automata theory) when one uses some arbitrary automaton that

recognizes the language and a different process for ¬nding the minimal automa-

ton. We shall develop another process and show that when using this process

on any automaton accepting the language, the minimal automaton is isomor-

phic to the intrinsic automaton and hence the minimal automata developed

for different automata for the same language produces isomorphic minimal

automata.

We shall now use an algorithm for “collapsing pairs of states” (without

altering the language being recognized) until no further collapsing is possible.

Thus producing a minimal automaton.

Here is the procedure:

Procedure

Step 1 For each set of pairs of states { p, q}, determine if there is a string with

length 0 that will take exactly one of these states into a ¬nal state (of course the

other into a non¬nal state). In case of (the) length zero string, this just means,

Automata

76

determine whether one of these states is ¬nal and the other is not. If so p and

q can NEVER be collapsed without altering the language accepted. Mark this

pair for “non-collapse”!

Step 2 For each remaining UN-MARKED pair { p, q} and each symbol b in

the alphabet, note {’( p, b), ’(q, b)). If ’( p, b) and ’(q, b) are distinct and

the pair they form was Marked in the PREVIOUS round then p and q can

NEVER be collapsed without altering the language recognized. Mark such pair

for “non-collapse”!

Repeat step 2 until, when the step is completed no new pairs have been Marked.

Note that for each pair { p, q} remaining unmarked at this stage: For any

string s of symbols of the alphabet, ’( p, s) and ’(q, s) (starting in states p

and q, the string s is read) must be either both ¬nal states or both non-¬nal

states.

Note that the following de¬nes an equivalence relation in the set S of states

of the original automaton: p ∼ q if { p, q} is an unmarked pair.

Collapse the state set S of the original automaton onto the set S/ ∼. A state

in S/ ∼ is ¬nal if it consists of ¬nal states of S. Each ’( p, s) = q of the original

automaton provides ’ ([ p], s) = [q] in the (minimized) automata where [ p],

[q] are the ∼ equivalence classes containing p and q.

Example 3.23 Let M be the deterministic automaton

b

s1

b

a

a s3

b

s0

b

s2 a

a

The unmarked pairs in step 1 are {s0 , s0 }, {s1 , s1 }, {s2 , s2 }, {s3 , s3 }, {s0 , s1 }, and

{s2 , s3 }. The unmarked pairs in the ¬rst use of step 2 are {s0 , s0 }, {s1 , s1 },

{s2 , s2 }, {s3 , s3 }, and, {s2 , s3 }, since there is an a-arrow from s0 to s1 and an

a-arrow from s1 to s2 and the states s1 and s2 are not in the unmarked pairs for

step 0. Further uses of step 2 produce no new results.

The equivalences classes are {{s0 }, {s1 }, {s2 , s3 }}, and we are ¬nished. In

the graph shown below, only one element is picked from each equivalence

class.

3.3 MDAs and syntactic monoids 77

Therefore a minimal deterministic automaton is the automaton

s1

a

a,b

s0

s2 a,b

b

Let M be the deterministic automaton

Example 3.24

a a

b s3

s1

a

s0 a b

b b

b

s2 s4

a

The unmarked pairs in step 1 are

{s0 , s0 }, {s1 , s1 }, {s2 , s2 }, {s3 , s3 }, {s4 , s4 }, {s0 , s2 }, {s0 , s1 } and {s1 , s2 }.

The unmarked pairs in the ¬rst use of step 2 are

{s0 , s0 }, {s1 , s1 }, {s2 , s2 }, {s3 , s3 }, {s4 , s4 } and {s1 , s2 }.

The second use of step 2 produces no new results so the equivalence classes are

{{s0 }, {s1 , s2 }, {s3 , s4 }}, and we are ¬nished.

Therefore a minimal deterministic automaton is the automaton where an

element is picked from each equivalence class.

a

a,b

a,b b

s0 s1 s3

Now, one can see that this minimized version of the arbitrary automaton

recognizing the language L is virtually identical with the intrinsic automaton

of the language.

Theorem 3.5 For a given regular language L, the two minimal reduced

automaton developed above accepting language L are isomorphic.

Automata

78

Proof M = ( , Q, s0 , ’ , F), the minimal reduced automaton developed by

the collapsing method is isomorphic to the intrinsic minimal automaton. So

Mi = ( , Q i , [1], ’i , Fi ). De¬ne f : Q ’ Q i by

—

f ([x] = {w ∈ : ’(x0 , w) ∈ [x]}.

Thus

—

f ([x] = {w ∈ : ’(s0 , w) = x for x ∈ [x]}.

Assume [x] = [y], then ’(x, u) ∈ F if and only if ’(y, u) ∈ F for u, v ∈

—

. Let f ([x]) = [w] and f ([y]) = ([w ]).

Then wu ∈ L if and only if w u ∈ L(= Fi ). Hence [w] = [w ] and f is

well de¬ned. Conversely, assume f ([x]) = f ([y]) then wu ∈ L if and only if

w u ∈ L(= Fi ) where ’(s0 , w) = x and ’(s0 , w ) = y. Hence ’(x, u) ∈ F if

and only if ’(y, u) ∈ F and [x] = [y]. Hence f is well de¬ned and one-to-one.

Finally we must show that f (’ ([x], a)) = ’i ( f ([x]), a),

’ ([x], a) = [’(x, a)],

and

’i ( f ([x]), a) = f ([x])a.

Let w ∈ f ([x], then ’(s0 , w) = x for x ∈ [x]. Let

’(x, a) = y ∈ [’(x, a)] = ’ ([x]], a)

and [y] = ’ ([x]], a). Now ’(s0 , wa) = y, so

f ([y])i = [wa]i = [w]i a = f ([x])a = [’i ( f ([x]), a)]

and so f (’ ([x], a)) = ’i ( f ([x]), a).

Corollary 3.1 For a given regular language, all reduced automata which

accept that language are unique up to isomorphism.

Instead of looking at the syntactic monoid from the intrinsic point of view,

as de¬ned above we examine it using an automaton. In particular we look at

minimal automata.

The transformation monoid of a deterministic automaton

M = ( , Q, s0 , ’, F)

is the image of a homomorphism • from — to a submonoid TM of the monoid

of all functions from Q to Q. If a ∈ , then •(a) = a where for each si ∈ Q,

¯

a(si ) = s j if there is an a-arrow from si to s j , i.e. ’(si , a) = s j . If a, b ∈ ,

¯

then ab = ab where ab(s) = a(b(s)). More speci¬cally, for u ∈ — , u(si ) = s j

¯ ¯ ¯ ¯

3.3 MDAs and syntactic monoids 79

if (si , u) — (s j , »). In other words, if the machine is in state si and reads u, then

it is in state s j .

Let M be the automaton

a

s1 b

s3

a

aa

b

s0 s2

b

b

then

a(s0 ) = s1 a(s1 ) = s2 a(s2 ) = s3

¯ ¯ ¯

a(s3 ) = s3 b(s0 ) = s2 b(s1 ) = s3

¯

b(s2 ) = s2 b(s3 ) = s2 .

For convenience, permutation notation is used here although the functions are

not usually permutations, since they are not one-to-one. Thus we have

s0 s1 s2 s3 s0 s1 s2 s3

a= and b =

¯

s1 s2 s3 s3 s2 s3 s2 s2

which we shall shorten to

0 1 2 3 0 12 3

a= and b = .

¯

1 2 3 3 2 32 2

0 1 2 3

By de¬nition let » =

¯ . We now perform the following products:

0 1 2 3

0 1 2 3 0 1 2 3 0123

ab = =

¯

1 2 3 3 2 3 2 2 3333

0 1 2 3 0 1 2 3 0123

ba = =

¯

2 3 2 2 1 2 3 3 3222

0 1 2 3 0 1 2 3 01 23

aa = =

¯¯

1 2 3 3 1 2 3 3 23 33

0 1 2 3 0 1 2 3 0123

bb = =

¯¯

2 3 2 2 2 3 2 2 2222

0 1 2 3 0 1 2 3 0123

a bb = = = ab.

¯¯¯ ¯

2 3 3 3 2 2 2 2 3333

Automata

80

Continuing this process and letting γ = ab, δ = a a, µ = bb, and ζ = ba, the

¯¯

¯ ¯¯ ¯

table for the transformation monoid TM is seen to be

» γ δ µ ζ

a b

¯

» » γ δ µ ζ

a b

¯

δ γ γ γ γ γ

a a

¯ ¯

ζ µ µ µ µ µ

b b

γ γ γ γ µ γ γ γ

δ δ γ γ γ γ γ γ

µ µ µ µ µ µ µ µ

ζ ζ µ µ µ µ γ γ

Example 3.25 Let M be the automaton

a b

b

s4

a

a s1 a

s0

ba

s3 b

b

s2

then

0 1 2 3 4 0 1234

a= and b = .

¯

1 3 1 4 4 2 1344

0 1 2 3 4

By de¬nition let » =

¯ . Let

0 1 2 3 4

0 1 2 3 4 01234

γ = ab = δ = aa =

¯ ¯¯

1 3 4 4 4 34344

0 1 2 3 4 0123 4

µ = bb = ζ = ba =

¯¯ ¯

3 1 4 4 4 1414 4

0 1 2 3 4 012 34

· = a ab = θ = bab =

¯¯ ¯

3 4 4 4 4 144 44

0 1 2 3 4 01 234

‘ = aba = ι = a bb =

¯¯¯

¯¯

3 4 3 4 4 43 444

0 1 2 3 4 01 234

κ = bbb = μ = abab = .

¯¯¯

4 1 4 4 4 34 444

3.3 MDAs and syntactic monoids 81

The table for the transformation monoid TM is seen to be

» γ δ µ ζ · θ ‘ ι κ μ

a b

¯

» » γ δ µ ζ · θ ‘ ι κ μ

a b

¯

δ γ · · ι ‘ · μ · · ι ·

a a

¯ ¯

ζ µ θ · κ ζ · θ · · κ ·

b b

γ γ μ ι μ · ι δ · μ · · ι ·

δ δ · · · · · · · · · · · ·

µ µ ζ κ θ · κ ζ · θ · · κ ·

ζ ζ θ θ · · · κ · · · · · ·

· · · · · · · · · · · · · ·

θ θ · · · · · · · · · · · ·

‘ ‘ · μ · · · · · · · · · ·

ι ι ‘ ι μ · ι ‘ · μ · · ι ·

κ κ ζ κ κ · κ ζ · θ · · κ ·

μ μ · · · · · · · · · · · ·

Theorem 3.6 Let M( , Q, s0 , ’, F) be a minimal deterministic automaton

and TM be the transformation monoid for M, then TM is ¬nite.

Proof Each element of TM is a function from Q to Q. If Q contains n elements,

then there are n n possible functions from Q to Q. Therefore the order of M is

less than or equal to n n .

Theorem 3.7 The syntactic monoid of a regular language L is isomorphic

to the transformation monoid of the minimal deterministic automaton M that

accepts L.

Proof Since, by the discussion following De¬nition 3.6, the syntactic monoid

can be considered to be the transformation monoid of the intrinsic minimal

deterministic automaton, and all minimal deterministic automata are isomorphic

to the intrinstic minimal deterministic automaton, the transformation monoid

is isomorphic to the syntactic monoid.

We now examine some of the properties of the syntactic monoid of a lan-

guage. Unlike the transformation monoid, as mentioned above, the syntactic

monoid of a language also exists for languages that are not regular.

—

De¬nition 3.7 Let φ be a homomorphism from to a monoid . A set

L ⊆ — is recognized by if φ ’1 φ(L) = L.

—

Let L ⊆ . The following conditions are equivalent.

Theorem 3.8

(i) L is a regular language.

(ii) The syntactic monoid Syn(L) is ¬nite.

(iii) L is recognized by a ¬nite monoid .

Automata

82

Proof (i)’(ii) If L is a regular language, then its syntactic monoid is isomor-

phic to the transformational monoid of the minimal automaton generating L

and hence is ¬nite.

(ii)’(iii) Assume φ is a homomorphism from — to Syn(L). If w ∈ L and

φ(w) = φ(w ), then uwv ∈ L if and only if uw v ∈ L for all u, v ∈ — . In

particular »w» ∈ L if and only if »w » ∈ L. So w ∈ L, if and only if w ∈ L.

Therefore φ ’1 φ(L) = L. Since Syn(L) is ¬nite, L is recognized by a ¬nite

monoid.

(iii)’(i) Assume L is recognized by a ¬nite monoid and let φ : — ’ .

To show L is a regular language, we construct an automaton M( , Q, s0 , ’, F)

that accepts L. Let Q = . De¬ne ’ : — ’ by ’(a, m) = mφ(a), for

all m ∈ and a ∈ . Let s0 = 1, the identity element of and F = φ( ). Then

w ∈ L(M) if and only if ’(w, 1) ∈ φ( ) if and only if w ∈ φ ’1 (φ( )) = L.

Exercises

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

automaton

b

s1 a,b

a

a

s3

s0 a

b

s2

b

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

automaton

b

s3

a a

s0 s1

b

a

b b

s2

a

3.3 MDAs and syntactic monoids 83

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

automaton

a b

s2

s1

a

s0 a a

b b