<<

. 3
( 9)



>>


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

<<

. 3
( 9)



>>