Lawson M.V. Finite Automata

Подождите немного. Документ загружается.

< previous page page_247 next page >

Page 247

Theorem 10.1.2. Choose

an idempotent such that for every idempotent we have that |

≤|

|. We claim that

is a minimal left ideal in

. Let be a non-empty left ideal in

. Then

in particular a finite subsemigroup and so contains an idempotent

. Because

is a left ideal of

have that

. But then . It follows that

and so

. By Proposition 11.2.14, we

have that

eTe

is a group in

and so in

. Now let

be the subgroup of

S(Y)

generated by the

permutations induced by elements of

on the set

. Define

α: G

→

α(a)

where

is the

permutation on

induced by

. This is clearly a surjective homomorphism.

(iii) If

is a non-trivial group in

then the claim follows by (i). Conversely, suppose that the conditions

of the claim hold. Then the result follows by (ii).

The result in (iii) above is important, because it enables us to connect our conjecture of Section 11.1

with the definitions of this section. Specifically the presence or absence of groups in a transition monoid

is the same as the presence or absence of elements inducing non-trivial permutations on subsets of the

set of states. The conjecture at the end of Section 11.1 can now be rephrased as follows: a language

over a one-letter alphabet is star-free iff its syntactic monoid contains no groups.

Finally, we characterise groups in Schützenberger products.

Proposition 11.2.16

Let M and N be monoids. Then every group in is isomorphic to a group in

Proof The function given by is a homomorphism. Let

(e, E, f)

an idempotent in . Then

is an idempotent in

M, f

is an idempotent in

and

. It follows

by Lemma 11.2.13 that

maps

H(e, E, f)

H(e, f)

. We use Proposition 11.2.7 to prove that

injective. Suppose there is an element in

H(e, E, f)

that maps to

(e, f)

. Such an element is of the form

(e, X, f),

where

We prove that

(e, X, f)

must be

(e, E, f)

. By assumption,

(e, X, f)

is invertible in

H(e, E, f)

so there

exists an element

(e, X′, f)

such that

Now

but

< previous page page_247 next page >

< previous page page_248 next page >

Page 248

and so

. Also,

but

and so . Hence

as required.

Exercises 11.2

1. Draw up Cayley tables for

2 and

2. Prove that if

and

are groups then

is a group. Show that the product of the groups ( , +)

and ( , +) is not cyclic.

3. Find all the maximal subgroups in

4. Let ( , ×) be the monoid of integers modulo

under multiplication. Prove that an element is

invertible if and only if it is coprime to

5. Let

be a monoid. For each define a function by

(x)fa

for each . Let

. Show that

is a sub-monoid of

T(M)

and that

is isomorphic to

6. Let

be a group. For each define a function by

(x)fa

for each . Show

that

is a permutation of

. Deduce that is a subgroup of

S(G)

. Show that

isomorphic to

7. Show that the only idempotent in a group is the identity. Now let

be a finite monoid with exactly

one idempotent. Prove that

is a group.

The second result is not true for infinite monoids. For example, A

is a monoid with exactly one

idempotent, but it is not a group

8. Let

α: S

→

be a homomorphism from the finite semigroup

onto the finite group

. Show that there

is a group

such that

α(H)

9. Let

and

be semigroups. Show that each maximal group in

is of the form

where

is a

maximal group in

and

is a maximal group in

10. Let

be a congruence on a group

and put

(1).

(i) Prove that

is a subgroup of

and that

−1

for each .

(ii) Prove that the admissible partition associated with

has as blocks the subsets of the form

where

< previous page page_248 next page >

< previous page page_249 next page >

Page 249

Now let

be any subgroup of

such that

−1

for all . Prove that is an

admissible partition of

Subgroups N satisfying the condition above are said to be

normal.

The results of this question show that

each congruence on a group determines and is determined by a normal subgroup of G. This means that

in group theory we need only work with normal subgroups rather than with the congruences they

determine.

11. Let

be a semigroup that contains an element

such that

for each . In addition,

suppose that for each element

there exists such that

. Prove that

is a group with

identity

11.3 Aperiodic semigroups

At the end of Section 11.1, we highlighted the absence or presence of groups in a syntactic monoid as

being crucial in determining whether the corresponding language was star-free or not. In Section 11.2,

we investigated groups in semigroups in general. In this section, we shall characterise those semigroups

all of whose groups are trivial. The key step in our characterisation will be an investigation of the sorts

of semigroups that can be syntactic monoids of recognisable languages over one-letter alphabets.

Theorem 11.3.1

Let S be a finite semigroup, and let be an arbitrary element. Then there are

positive integers m and r such that the elements a

,…, am,…, am

−1

are distinct, but am

r=am

Furthermore, the elements Ca

{am,…, am

−1

} form a cyclic group of order r in S

Proof Consider the subsemigroup

{a, a

,…}

. Because

is finite there must be a power of

say

ai,

which is repeated later on, say

where

≠

. Thus the set,

is non-empty, and so has a smallest element which we denote by

. The set,

is therefore non-empty, and so has a smallest element which we denote by

. By construction the

elements

,…, am

−1 are distinct. Put

From

and induction, we deduce that

< previous page page_249 next page >

< previous page page_250 next page >

Page 250

for all . Let

≥

be any number. By the Remainder Theorem, we may write

Thus

It follows that

is a subsemigroup of

. We show that

is a cyclic group in

and to do this we

shall use the group (

, +). Define by

θ(am

i′,

where and

i′

(mod

). The

numbers

m,…, m

−1) are

consecutive numbers and so are congruent modulo

to the numbers 0,…,

−1 in some order. Thus

is a bijection. We show that it is a homomorphism. Let 0≤

i, j

≤

−1. Then

where

It follows that

Let

where

. Then

Thus

It follows that

But

and

Thus

i′

j′

(mod

). Hence

is a homomorphism, and so an isomorphism of semigroups. But a

semigroup isomorphic to a group is itself a group. Thus

is a group isomorphic to under addition.

Let

be a finite semigroup and . Then the number

is called the

index of a

and the number

called the

period of a

We can now return to the question of when a semigroup contains only trivial groups.

< previous page page_250 next page >

< previous page page_251 next page >

Page 251

Theorem 11.3.2

Let S be a finite semigroup. Then the following are equivalent:

(i)

The relation is equality.

(ii)

The maximal subgroups in S are trivial

(iii)

For each element the period of a is

(iv)

There exists n

such that an

for all

Proof (i) (ii). Immediate from Proposition 11.2.11.

(ii)

(iii). Suppose that the maximal subgroups of

are trivial. Then for each the group

Ca,

defined in the proof of Theorem 11.3.1, must be trivial. Hence each element has period 1.

(iii)

(iv). Suppose that each element of

has period 1. Let

| and let . We claim that

+1. Observe that the

+1 elements

a, a

,…, an

+1 cannot all be distinct. Thus the index of

is at

most

. If the index of

then the result is immediate. If the index is

then .

Thus

an=an

(iv)

(i). Let . Then there exist such that

We can therefore write

axd

and so

anxdn

for all

≥1. By assumption, we can choose

such that

+1. Then

ax=a(anxdn)

xdn

anxdn

. Thus

. But

as well. We have proved that

A semigroup

aperiodic

if every group in

is trivial. If the semigroup is a subsemigroup of a full

transformation monoid, we can use Proposition 11.2.15 to determine if it is aperiodic. Here is an

alternative algorithm using Theorem 11.3.2.

Algorithm 11.3.3 Let

be a finite semigroup.

(1) Choose

and calculate the subsemigroup

(2) There are now several cases:

• If the period of

is not 1 then

is not aperiodic and the algorithm terminates.

• If the period of

is 1 and

+ then

is aperiodic and the algorithm terminates.

• If the period of

is 1 and

≠

then we replace

+ and repeat (1).

< previous page page_251 next page >

< previous page page_252 next page >

Page 252

A detailed analysis of the problem of determining whether a monoid is aperiodic or not is the subject of

[26]. Our next result summarises some important properties of aperiodic monoids.

Theorem 11.3.4

Let S and T be monoids.

(i)

If S is aperiodic and T is a submonoid of S then T is aperiodic.

(ii)

If S is aperiodic and T is a homomorphic image of S then T is aperiodic.

(iii)

If S is aperiodic and T is a monoid dividing S then T is aperiodic.

(iv)

If S and T are aperiodic then S

T is aperiodic

(v)

If S and T are aperiodic then

is aperiodic.

Proof (i) By assumption

contains only trivial groups. It is immediate that

can only contain trivial

groups.

(ii) Let

θ: S

→

be a surjective monoid homomorphism. Let . Then there exists such that

θ(s)

. By assumption, there exists

>0 such that

+1. But

θ(sn)

and

θ(sn

)

+1. Thus

+1. It follows that

is aperiodic by Theorem 11.3.2.

(iii) This is immediate by (i) and (ii) above.

(iv) A group in

is of the form

where

is a group in

and

is a group in

by Question 9 of

Exercises 11.2. Thus

is aperiodic if

and

are.

(v) This follows from Proposition 11.2.16 and Question 9 of Exercises 11.2.

Exercises 11.3

1. Find the index and period of each element in

11.4 Schützenberger’s theorem

In this section, we shall characterise star-free languages by means of their syntactic monoids. The proof

of the theorem is in two parts: first, if

is star-free, then its syntactic monoid

M(L)

is aperiodic; second,

is a recognisable language with an aperiodic syntactic monoid

M(L),

then

is star-free. The proof of

the first half is now easy.

Theorem 11.4.1

The syntactic monoid of a star-free language is aperiodic.

Proof Let

be a finite alphabet. The star-free languages are constructed from the basic languages

, ε

and

where

using the Boolean operations and product of languages. It is easy to check that the

syntactic monoids of the basic languages are aperiodic. Our induction hypothesis is that any

< previous page page_252 next page >

< previous page page_253 next page >

Page 253

language described by a star-free, generalised regular expression with at most

operators has an

aperiodic syntactic monoid. Let

be a star-free generalised regular expression with

+1 operators. Then

s′

. Each of the star-free expressions

and

has at most

star-free

operators. Thus the syntactic monoids of

L(s)

and

L(t), M

and

respectively, are both aperiodic. We

now prove in each case that the syntactic monoid of

L(r)

is aperiodic. If

s′

then

L(s)

recognises

s′

Proposition 10.2.8(i); in fact, in this case

L(s)

is also the syntactic monoid of

s′

. Thus

L(r)

has a

syntactic monoid that is aperiodic.

If r

t or r

then

L(r)

is recognised by

. But

aperiodic by Theorem 11.3.4(iv), and the syntactic monoid of

L(r)

divides

by Theorem 10.2.6,

consequently by Theorem 11.3.4(iii), the syntactic monoid of

L(r)

is aperiodic. Finally, if

then

L(r)

is recognised by a monoid

which is a subsemigroup of by Proposition 10.2.11. But is

aperiodic by Theorem 11.3.4(v), and so

is aperiodic by Theorem 11.3.4(i). The syntactic monoid of

L(r)

divides

by Theorem 10.2.6, consequently by Theorem 11.3.4(iii), the syntactic monoid of

L(r)

aperiodic. It follows that in all cases the syntactic monoid of

L(r)

is aperiodic.

The result above is already useful.

Example 11.4.2 Let

{a}

. A recognisable language

over

has the form

Y(ap)

* where

and

are finite languages. We claim that

is star-free if and only if

=0, 1. If

=0, 1, then we established

that

is star-free in Section 11.1. We shall now prove that if

≥2 then

is not star-free. To do this, we

shall prove that the syntactic monoid of

is not aperiodic, which gives the required result by Theorem

11.4.1. As we saw in the proof of Theorem 5.2.2, the minimal automaton A for

consists of a stem, and

a cycle of

states

,…, rp

. It follows that the letter

induces a non-trivial permutation on the set

…, rp}

. Consequently, the transition monoid of A contains a non-trivial group by Proposition 11.2.15(iii).

But the transition monoid of the minimal automaton of

is isomorphic to the syntactic monoid of

Theorem 9.4.3. It follows that the syntactic monoid of

is not aperiodic, and so

is not star-free by

Theorem 11.4.1.

From this result, it follows that the language

(aa)

* is not star-free. This should be contrasted with the

language

(ab)

which we explicitly showed to be star-free in Example 11.1.1.

The proof of the converse, that an aperiodic syntactic monoid implies a star-free language, is much

harder in the case of a general alphabet and we shall need a number of preparatory steps.

Lemma 11.4.3 (Cancellation property)

Let M be an aperiodic monoid. Suppose

are such

that q

pqr

Then q

< previous page page_253 next page >

< previous page page_254 next page >

Page 254

Proof The monoid

is aperiodic, and so by Theorem 11.3.2 there is a positive integer

such that

+1 for each . From

pqr

we get by induction that

pnqrn

. Thus

qrn

p(pnqrn)

. A similar argument shows that

qr.

Lemma 11.4.4

Let M be a monoid, and . Put

Then W(a) is the largest ideal in M that does not contain a.

Proof Suppose that

W(a)

is empty. We prove that every non-empty ideal of

contains

. Let

be a

non-empty ideal of

and let . Then . If then

but this contradicts the

assumption that

W(a)

is empty. Thus and so .

Suppose that

W(a)

is non-empty. Let and let . We show that . If

then from we get that

which is a contradiction. Thus

. We may similarly show that and it follows that

W(a)

is an ideal. We now prove

that

W(a)

is the largest ideal in

not containing

. Let

be a non-empty ideal of

that does not

contain

. Let . Then

because

is an ideal. Since

does not contain a neither can

MbM

It follows that . Hence .

We now have the following crucial property of aperiodic monoids.

Proposition 11.4.5

Let M be an aperiodic monoid. Then

for each .

Proof From Lemma 11.4.4, the element a belongs to the complement of

W(a)

and it is evident

that . Thus the left-hand side is always contained in the right-hand side. To prove the

reverse containment, let . Then

and

ubv

for some . Then

ubv

(uq)av,

and so by the cancellation property

uqa

. Thus

uap

and so by the

cancellation property

. Hence

as required.

Suppose that

is a language whose syntactic monoid is aperiodic. In particular, there is a monoid

homomorphism

where

is aperiodic and a subset such that . We can

therefore write . So to show that

is star-free it is enough to prove that languages of

the form

are star-free, and this will be the approach we adopt.

< previous page page_254 next page >

< previous page page_255 next page >

Page 255

Let

be a monoid and let . By the

rank of a,

denoted r

(a),

we mean the number |

MaM

|. If two

elements

and

belong to the same , then they must have the same rank, because by

definition

means that

MaM

MbM

. Since

MaM

is a subset of

the largest the rank can be is |

This is reached by the identity because

. In an aperiodic monoid, the identity is the only

element reaching maximum rank, as we now show.

Lemma 11.4.6

Let M be an aperiodic monoid. If is such that

(a)

= |

then a

=1.

Proof From |

MaM

|=|

|, and we have that

MaM

because

is finite. Thus there are

such that 1=

paq

. From 1=

(pa)

and the cancellation property for aperiodic monoids, we

have that 1=

. And from 1=

we get 1=

by the cancellation property.

The next result tells us that for the element of maximum rank, the inverse image will be star-free.

Lemma 11.4.7

Let be a monoid homomorphism to an aperiodic monoid. Then

is a

star-free subset of A

Proof Define

. We claim that

which is clearly star-free.

Let

and let . Suppose that , so that

By the cancellation property for aperiodic monoids, we have that

By the cancellation property applied to we have that . Thus in particular

, which is a contradiction. Hence none of the strings in

* can be mapped to 1.

Now let be a non-empty string. Then

…an

where . Suppose that .

Then for at least one

we must have . But then

and so , which is a

contradiction. We have therefore proved the result.

In order to prove our main theorem, it remains therefore to prove that the set

is star-free for

each element

of our monoid, which is not of maximum rank. Our approach will be to write the set

as a ‘combination’ of sets where the rank of n is strictly greater than the rank

< previous page page_255 next page >

< previous page page_256 next page >

Page 256

and where by ‘combination’, we mean using only Boolean operations or concatenation.

The following is a technical lemma whose significance will soon become clear.

Lemma 11.4.8

Let be a monoid homomorphism to an aperiodic monoid M. Let

(i)

Let

and

be such that

and

Then

(n)

(m)

(ii)

Let and be such that

and

Then

(n)

(m)

(iii)

Let

and

be such that

Then

(n)

(m)

Proof (i) Observe that

so that r

(m)

≤r

(n)

. Suppose that r

(m)

(n)

. By

finiteness,

MmM

MnM

. It follows that we can write

umv

for some . Since

also have that

for some . Thus

umv

un(pv)

. By the cancellation property for aperiodic

monoids, we therefore have that

npv

. Thus

mv,

which implies that . But this is a

contradiction. It follows that r

(n)

(m)

as required.

The proof of (ii) is simply the left-right dual of the proof of (i).

(iii)

Let

and . Clearly r

(m)

≤r

(n)

. Suppose that r

(m)

(n)

Then

umv

for some . In addition, we have from our assumptions that

for some . Now . Thus by the cancellation property for

aperiodic monoids, we have that . But then

which contradicts our assumptions. It follows that r

(n)

(m),

as required.

The key argument in our proof of Schützenberger’s theorem is the following.

Proposition 11.4.9

Let be a monoid homomorphism to an aperiodic monoid M. Let

. Then

where U, V and W are subsets of A

defined as follows:

•

The set U is the union of sets of the form

where , ,

but

< previous page page_256 next page >