Lawson M.V. Finite Automata

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

< previous page page_267 next page >

Page 267

(4)

Finite groups.

This needs a little work. The proof of (VM2) follows from Lemma 11.2.13, and the

proof of (VM3) follows from Question 2 of Exercises 11.2. The proof of (VM1) is more involved. Let

a submonoid of the finite group

. We need to show that

is a group. Notice that we are not assuming

that

is a subgroup of

. We therefore have to prove that for each the inverse of

also belongs

. Because

is finite,

is finite and so by Theorem 10.1.2, there is an integer

≥1 such that

an idempotent. Now

is a group and so has exactly one idempotent, the identity, and

is a

submonoid of

and so it has exactly one idempotent, the identity. It follows that

=1. Thus

−1

=1=

ggn

−1

and so

as required.

We shall now describe a way of constructing further examples of pseudovarieties of monoids. Let be

any collection of monoids. I shall define four operations that may be applied to to yield a potentially

new class of monoids.

• Define S( ) to be the collection of all submonoids of elements of .

• Define H( ) to be the collection of all homomorphic images of elements of .

• Define P( ) to be the collection of all finite products of elements of .

• Define I( ) to be the collection of all monoids that are isomorphic to elements of .

In the lemma below, IP is the operation P followed by the operation I. We shall explain after the proof

why we use this and not P on its own.

Lemma 12.1.4

Let

be any one of the operations

H, S,

IP.

Let ,

collections of monoids

Then the following three conditions hold:

(i) .

(ii) then .

(iii) .

Proof We shall prove (i), (ii), and (iii) for the operation H and leave the proofs of the two remaining

cases as exercises.

(i) This follows from the fact that the identity function is a homomorphism.

(ii) If

is a homomorphic image of a monoid in , then it is trivially a homomorphic image of a monoid

(iii) We have to show that . Let . Then

is a homomorphic image of a

monoid

and

is a homomorphic image of a monoid . Thus

is also a homomorphic

image of

since

< previous page page_267 next page >

< previous page page_268 next page >

Page 268

the composition of two monoid homomorphisms is a monoid homomorphism by Proposition 9.1.8(iii).

Thus , as required.

Remark We now explain why we considered the operation IP above and not the operation P. It is true

that P satisfies both properties (i) and (ii). The problem is (iii). If then

. Thus . However, this monoid is isomorphic to the

monoid

1×

2×

3×

4 in P( ) not equal to it.

The next lemma describes some relations amongst our operations.

Lemma 12.1.5

Let be a collection of monoids.

(i) .

(ii) .

(iii) .

Proof (i) Let . Then

is a submonoid of a monoid

that is a homomorphic image of a

monoid

. By Proposition 9.1.8,

is a homomorphic image of a submonoid of

which proves the

inclusion.

(ii) Let . Then

1×

…

where each

is a submonoid of a monoid . However,

1×

…

is a submonoid of

1×

…

by Lemma 10.1.10. Thus

is a submonoid of a finite product of

monoids belonging to , as required.

(iii) Let . Then

1×

…

where each

is a homomorphic image of a monoid . But

1×

…

is a homomorphic image of

1×

…

by Lemma 10.1.10. Thus

is a homomorphic image

of a finite product of monoids from , as required.

Theorem 12.1.6

Let be a collection of monoids. Then

HSP( )

is a pseudovariety of monoids

containing , and is in fact the smallest pseudovariety of monoids containing

Proof By Lemma 12.1.4 and the remark following, we have that

Thus

as claimed. Next we prove that HSP( ) is closed under the operations H, S, and P, which will show

that it is a pseudovariety. Closure under H follows from Lemma 12.1.4(iii) since H2=H. Closure under S

follows from Lemma 12.1.5(i) and Lemma 12.1.4(iii) because

< previous page page_268 next page >

< previous page page_269 next page >

Page 269

Finally, we prove closure under P. We have that

using Lemma 12.1.5(iii) and (ii). It is clear that for any collection of monoids we have that

. Thus

But by Lemma 12.1.4(iii), we have that

It is clear that for any collection of monoids we have that

Thus

But then by Lemma 12.1.5(i) and Lemma 12.1.4(iii) we have that

Thus

as required. To show that HSP( ) is the smallest pseudovariety containing , let be any

pseudovariety containing . Then .

The pseudovariety HSP( ) is called the

pseudovariety of monoids generated by

. The following

provides a slightly more succint way of describing the pseudovariety generated by , and is left as an

exercise.

Proposition 12.1.7

A monoid belongs to the pseudovariety generated by if and only if it divides a

finite product of monoids belonging to

What we have done for monoids, we shall do for languages. Before that we prove a technical lemma,

which will partially motivate the definition that follows. On a point of notation: it is easy to check that

−1

L)v

−1=

−1

(Lv

−1

)

so that the expression

−1

−1 is unambiguous.

Lemma 12.1.8

Let be a recognisable language with syntactic monoid M(L) and where α:

*→

M(L) is the natural monoid homomorphism associated with the syntactic congruence σL

Then for

each

the set

for some x, can be written as a finite Boolean combination of the languages u

−1

, where

< previous page page_269 next page >

< previous page page_270 next page >

Page 270

Proof For

define

the set of contexts of

. Thus . We prove that

We prove first that the left-hand side is contained in the right-hand side. Let . If

then and so . Hence . If then and so

which

implies . It follows that the left-hand side is contained in the right-hand side.

We now prove that the right-hand side is contained in the left-hand side. Let

be an element of the

right-hand side. Suppose

. Then and so from which we get .

Now suppose that

. Then . Thus and so . It follows that

The

finiteness

of this Boolean combination follows from the fact that by Proposition 7.5.5(i) the left or

right quotient of a recognisable language is recognisable and by Theorem 7.5.5(ii) a recognisable

language has only a finite number of left and right quotients.

The definition below is not an obvious one, although it is partially motivated by Lemma 12.1.7. We shall

see, however, why it is correct when we prove the Variety Theorem. A

variety of languages

is defined

to be a family of languages

where

ranges over all finite alphabets

such that the following

conditions hold:

(VL1)

For each finite alphabet

the set of languages is a subset of

which is closed under the

Boolean operations.

(VL2)

For each finite alphabet

each language and each letter

both

−1

and

−1

belong to

(VL3)

α: A

*→

* is a monoid homomorphism and then .

Thus a variety of languages is a collection of sets of languages over different alphabets that fit together

under taking inverse images. Our goal is to show that there is a bijection between the collection of

pseudovarieties of monoids and the collection of varieties of languages. We now define two functions.

• Let

be a pseudovariety of monoids. Define as follows: for each finite alphabet

put

< previous page page_270 next page >

< previous page page_271 next page >

Page 271

• Let be a variety of languages. Define to be the pseudovariety of monoids generated by the

collection of all syntactic monoids of languages belonging to .

The following result ensures that is a variety of languages.

Proposition 12.1.9

Let be a pseudovariety of monoids. Then is a variety of languages.

Proof We prove first that is the set of all languages over

which are recognised by monoids in

. If

then and

M(L)

recognises

by Lemma 10.2.4. Now let be any

language recognised by a monoid

in . Then

M(L)

divides

by Theorem 10.2.6. But and so

because pseudovarieties are closed under division by Proposition 12.1.7. Thus . We

now have to check that (VL1), (VL2), and (VL3) hold. These verifications follow from Proposition 10.2.8.

We can now prove our main result due to Eilenberg and Schützenberger.

Theorem 12.1.10 (The Variety Theorem)

The functions and are mutually inverse. There is

therefore a bijection between the collection of all monoid pseudovarieties and the collection of all

language varieties.

Proof We show first that is injective. Let and be two pseudovarieties of monoids such that

. Let . Then by Theorem 12.1.2,

divides a finite product

M(L

)

…

M(Ln),

where

each language

is recognised by

for some alphabet

. It follows from the proof of Proposition

12.1.9 that . By assumption . Thus . By definition

and so . But

divides

M(L

)

…

M(Ln)

and so because

pseudovarieties are closed under division. We have shown that

. By symmetry, the reverse

inclusion holds, and we have proved the claim.

Let be a variety of languages. We show that

which implies that is surjective. It is

immediate from the definitions that for each alphabet

. We prove the reverse inclusion.

Let . Then

M(L)

divides a product of the form

M(L

)

…

M(Ln),

where for

some

nite alphabets

. We shall prove that . Because

M(L)

is the syntactic monoid of

and

divides

we know by Theorem 10.2.6 that

recognises

. Thus there is a monoid homomorphism

and a subset such that . Let

πi: M

→

M(Li)

be the projection

homomorphism, and let

be the natural homomorphism corresponding to the syntactic

congruence

. Define . We therefore have the following diagram of monoid homomorphisms

where the unbroken lines are

< previous page page_271 next page >

< previous page page_272 next page >

Page 272

the known functions:

By Proposition 10.2.3, there is a monoid homomorphism such that . Let .

Then

,…, mn)

where each . The proof that occurs in stages:

(1)

by Lemma 12.1.8 and (VL1) and (VL2).

(2)

by (VL3) and (1).

(3)

by (VL1) and (2). We leave the proof of this as an exercise.

(4)

by (VL1) and (3).

We have therefore proved that

as required.

We have proved that

is a bijection, and that for each variety of languages . Let be a

pseudovariety of monoids and suppose that . Then . Thus

and so . It follows that and are mutually inverse operations.

Exercises 12.1

1. Prove Lemma 12.1.1(1): if is a set of congruences on a semigroup

then a

congruence on

2. Show that finite commutative monoids form a pseudovariety.

3. Complete the proof of Lemma 12.1.4 for S and IP.

4. Show that P satisfies conditions (i) and (ii) of Lemma 12.1.4.

5. Prove Proposition 12.1.7: a monoid belongs to the pseudovariety generated by iff it divides a finite

product of monoids belonging to .

6. Show that the intersection of any family of pseudovarieties of finite monoids is a pseudovariety of

finite monoids. Show that the intersection of all pseudovarieties of finite monoids containing a class of

finite monoids is precisely the pseudovariety generated by .

7. Prove (3) in Theorem 12.1.10.

< previous page page_272 next page >

< previous page page_273 next page >

Page 273

8. Let be a pseudovariety of finite groups. Let be the collection of all finite monoids whose

maximal groups belong to . Show that is a pseudovariety of finite monoids. You will find

Exercises 11.2, Questions 8 and 9 helpful.

12.2 Equations for pseudovarieties

A pseudovariety of monoids is a collection of monoids closed under homomorphic images, finite

products, and submonoids. In this section, we shall derive an alternative characterisation of

pseudovarieties which is of practical importance.

is a relation on a monoid

then we can define the intersection of all congruences on

that

contain

. Since the intersection of congruences is a congruence by Lemma 12.1, the relation is a

congruence. It is clear that

is the smallest congruence on

containing

. We say that

ρ generates

the congruence . If a is a congruence such that where

is finite, then we say that

finitely

generated

Proposition 12.2.1

Let σ be a congruence on A

such that A

σ is finite

Then σ is finitely generated.

Proof Denote the

-congruence class of

[x]

. Let

l[x]

stand for the length of the shortest strings in

[x]

. Put . Since there are only finitely many congruence classes, this number is

well-defined and finite. By construction, each congruence class contains a string of length strictly less

than

. Put

For each

such that |

|≤

there exists such that |

and

xσy

. We prove that .

Since

it follows that . Suppose that that the reverse inclusion did not hold; we shall obtain a

contradiction. Assume therefore that for some

and

we have that

uσv

but . Choose such a

pair

(u, v)

with |

|+|

| minimal. Suppose that |

|≥

. Then

xu′

for some

u′

such that |

u′

. By

definition, there exists such that and |

v′

|<k. From we get that

and so

xu′σxv′

. It follows that

xv′σv

. Observe that

for if it were then

which is a contradiction. In addition, |

xv′

|<|

| since

xu′

and |

v′

and |

u′

. However,

the pair

(xv′, v)

now contradicts the minimality of the pair

(u, v)

. It follows that |

. Now repeat the

argument above with

. It follows that uσv and |

|, |

. Hence and so

which is a

contradiction.

< previous page page_273 next page >

< previous page page_274 next page >

Page 274

We shall now describe a method for describing pseudovarieties of semigroups. We have already met

examples of this method. For instance, a semigroup

is commutative if

for all . This can

be expressed more formally as follows. Let

and

be two variables. Then a semigroup is commutative

if the equation

holds whenever we substitute

for

and

for

where

and

are any elements

. We now generalise this idea.

Let

be a countably infinite alphabet; this is the only place where we use an infinite alphabet. Let

. We say that a monoid

M satisfies the equation u

α(u)

α(v)

for every monoid

homomorphism

α: A

*→

. Just as in the case of

finite, a monoid homomorphism from

* is

determined by its values on the elements of the set

. It follows that this formal definition says precisely

that

is satisfied by

if, whenever we substitute the symbols in

and in

by elements of

the

resulting two elements of

are always equal.

It is easy to show that the collection of all finite monoids

(u, v)

satisfying the equation

u=v

is a

pseudovariety. The intersection of any family of pseudovarieties is a pseudovariety, so if we have a

sequence of equations

(un

vn)n

≥1 whether finite or infinite, then is also a

pseudovariety. We say that is

defined

by the equations

(un

vn)n

≥1. In other words, a monoid

belongs to if it satisfies all of the equations

un=vn

. I shall write for the pseudovariety

of monoids satisfying all the equations

Example 12.2.2 The pseudovariety defined by

(xy

yx)

is the pseudovariety of commutative

monoids. The pseudovariety

is the pseudovariety of all monoids in which every element is

idempotent: the

band monoids

. A commutative band is called a

semilattice

. Thus

(xy

yx, x

is the

pseudovariety of semilattice monoids.

The notion of a pseudovariety being defined by a set of equations turns out not to be sufficient to

describe all pseudovarieties. To do this, we need a more general notion.

Suppose we have an infinite sequence of equations

(un

vn)n

≥1. We say that a monoid

M ultimately

satisfies

these equations if there is a

such that

satisfies

for all

≥

. The collection of monoids

ultimately satisfying the equations

(un

vn)n

≥1 is also a pseudovariety.

Example 12.2.3 By Theorem 10.3.2, a finite monoid

is aperiodic iff

+1 for some

>0 and for

all

. Thus a finite monoid is aperiodic iff it ultimately satisfies the equations

(xn

>0.

We now have the following alternative characterisation of pseudovarieties of finite monoid.

Theorem 12.2.4

Every pseudovariety of finite monoids is ultimately defined by a sequence of

equations.

< previous page page_274 next page >

< previous page page_275 next page >

Page 275

Proof Let be a pseudovariety of finite monoids. Let

, a

,…}

be a countably infinite alphabet.

Put

,…an}

. Clearly is a submonoid of

*. All the monoids in are finite. Each finite monoid

elements is isomorphic to one defined on the set

={1, 2,…,

}. Thus each monoid in of size

is isomorphic to a monoid defined on

. We can clearly list all the monoids defined on

that belong

to . There is therefore a list of monoids,

of non-decreasing size such that each of them belongs to and each monoid in is isomorphic to

exactly one of them.

For each

≥1, put

1×

…

. There are only finitely many monoid homomorphisms

because

and

are both finite and each such homomorphism is determined by its values on the set

. Let

ρn

be the congruence defined on as the intersection of all congruences where is a

monoid homomorphism. By the above there are only finitely many such congruences. By Lemma 12.1.1,

is isomorphic to a submonoid of the finite product of the finite monoids . Each of these

monoids is isomorphic to a submonoid of

. It follows that is isomorphic to a submonoid of a

product of finitely many copies of

with itself. In particular,

ρn

is finite. By Proposition 12.2.1, the

congruence

ρn

is finitely generated. Thus there is a finite set generating

ρn

. Put

. We claim that is ultimately defined by the equations

Let

. Then there exists

such that

is isomorphic to a submonoid of

for every

≥

. By

construction,

satisfies the equations

for each

≥

. It follows that

satisfies the equations

for

each

≥

To prove the converse, let

be a finite monoid that satisfies

for each

≥

for some

. Choose

≥max

(k, |M|)

. Let be a surjective monoid homomorphism. By definition for all

. It follows that implies that . There is therefore a surjective monoid

homomorphism from to

by Proposition 9.2.12. But is isomorphic to a submonoid of a

product of finitely many copies of

. Thus

divides a product of finitely many copies of

. Hence

Exercises 12.2

1. Show that

is a pseudovariety.

2. Show that the collection of monoids ultimately satisfying the set of equations

(un

vn)n

≥1 is a

pseudovariety.

3. Prove that if is a pseudovariety generated by a single monoid, then is defined by a sequence of

equations (rather than merely being ultimately defined).

4. Let be one of Green’s relations. We say that a finite monoid is

< previous page page_275 next page >

< previous page page_276 next page >

Page 276

is the equality relation. Thus by Theorem 11.3.2, the finite aperiodic monoids are just the

ones. Prove the following:

(i) A finite monoid is iff it satisfies

(xy)nx

(xy)n

for some

>0.

(ii) A finite monoid is

iff it satisfies

y(xy)n

(xy)n

for some

>0.

(iii) A finite monoid is

iff it satisfies

(xy)nx

(xy)n

y(xy)n

for some

>0.

Show also that a finite monoid is

iff it satisfies

(xy)n

(yx)n

and

+1 for some

>0.

12.3 Summary of Chapter 12

•

Pseudovariety of monoids:

A non-empty collection of finite monoids closed under taking submonoids,

homomorphic images, and finite products.

•

Variety of languages:

A collection of languages over each finite alphabet, where the set of languages

over a fixed alphabet is closed under the Boolean operations and the taking of left and right quotients.

The whole ensemble is closed under inverse images of monoid homomorphisms between free monoids.

•

The Variety Theorem:

Each pseudovariety is paired with a unique variety of languages and vice versa.

•

Pseudovarieties and equations:

Each pseudovariety is ultimately defined by an infinite sequence of

equations. This means that each monoid in the pseudovariety satisfies all the equations from some point

on.

12.4 Remarks on Chapter 12

In writing this chapter, I have consulted both Lallement [77] and Pin [103] constantly. The proof of

Theorem 12.1.6 is adapted from [70]. Theorem 12.1.10 is proved in [40] and Theorem 12.2.4 in [41].

Both results are due to the combined efforts of two outstanding mathematicians: Eilenberg and

Schützenberger.

I indicated in Section 12.1, that the definition of a variety of languages is perhaps not the most obvious,

although all three conditions are certainly plausible: condition (VL1) is natural from the point of view of

the results we proved back in Section 2.6; condition (VL2) highlights the importance of taking left and

right quotients, something we first met in Chapter 7; Lemma 12.1.8 is further evidence for the

importance of the Boolean operations taken in tandem with left and right quotients; and, finally,

condition (VL3) is reasonable,

< previous page page_276 next page >