<< стр. 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
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 [] 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 , , П’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)СОДЕРЖАНИЕ >>