Lawson M.V. Finite Automata

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

< previous page page_187 next page >

Page 187

Examples 8.4.2 Monoids have occurred in a number of places throughout this book.

(1) In Section 1.1, we showed that for any alphabet

the set

* equipped with the binary operation of

concatenation is an associative binary operation with identity

. Thus

* is a monoid. When

consists

of one letter only, the monoid

* is commutative, but in general it is non-commutative. In all cases

is infinite.

(2) If

is any language, then

and

implies that (Question 4 of Exercises 1.3).

Thus

* is a monoid.

(3) Let

be an alphabet. The pair (

+) is a monoid with identity (Proposition 5.1.5).

(4) Let

be an alphabet. The pair (

·) is a monoid with identity

{ε}

(Proposition 5.1.5).

(5) Let

be a set. Then the pair (

T(X),

) is a monoid with identity

ι,

the identity function on the set

by Proposition 8.1.3.

(6) Consider the set of all

matrices with entries from . Then with matrix

multiplication as the binary operation, we have an associative operation with identity the

matrix all

of whose entries are except the leading diagonal that instead consists entirely of

’s.

Examples (3) and (4) can be generalised. Let

be a semigroup. Then is a semigroup in two

different ways. First under the operation + of union: (

+) is a commutative monoid with identity .

Second under

product of subsets,

which is defined as follows: if

then define

Then (

·) is a semigroup with zero . We usually denote this binary operation by concatenation. If

is a monoid then (

·) is a monoid with identity {1}. These two operations interact nicely with

each other:

Just as we did in the case where

we shall usually denote subsets of

of the form

{s}

. We

can therefore form products such as

where and . If then we define

and

XXn

−1 for

≥1. If

is a monoid with identity 1, we define

0={1}.

< previous page page_187 next page >

< previous page page_188 next page >

Page 188

To conclude this section, we return to what we did in Sections 8.1–8.3 and apply our new terminology.

Let A be an automaton with state set

and input alphabet

. By Proposition 8.1.4, the set of functions,

is closed under composition of functions and contains the identity function. Since the composition of

functions is associative by Proposition 8.1.3, it follows that

(A) is a monoid. It is called the

transition

monoid

of the automaton A. The set of representatives of an automaton forms a monoid by Proposition

8.3.2, called the

monoid of representatives

. The transition monoid and the monoid of representatives are

closely related because . We shall explain the nature of this relationship in Chapter 9.

Exercises 8.4

1. Show that

1 really is a monoid.

2. Let

be a semigroup. Prove that both (

+) and (

·) are semi-groups. Show also that

·(

for all

A, B,

3. Let

={−1, 1} with multiplication as product. Then

is a monoid. Draw up the Cayley table for

with respect to product of subsets.

4. An element

is said to ‘fix the letter 1’ if 1

=1. Prove that the composition of two functions

that fix the letter 1 also fixes the letter 1. Deduce that the elements of

that fix the letter 1 form a

monoid under composition. Draw up the Cayley table for those elements of

3 that fix the letter 1.

8.5 Summary of Chapter 8

•

The transition monoid of an automaton:

This is the set of all functions on the set of states induced by

input strings. It is closed under composition of functions. The elements of the transition monoid can be

found in a way analogous to the calculation of the accessible states of an automaton via its transition

tree.

•

Representatives and relations:

Each element of the transition monoid is induced by a string and, if we

find the smallest such string in the tree order, we get a bijection between elements of the transition

monoid and a finite set of strings. These are called representatives. In addition, for each representative

and each symbol

the string

must be equivalent to a unique representative

. We call

relation.

< previous page page_188 next page >

< previous page page_189 next page >

Page 189

•

Semigroups and monoids:

A semigroup is a set equipped with an associative binary operation. A

monoid is a semigroup with an identity.

8.6 Remarks on Chapter 8

In writing this chapter, I found inspiration by reading Chapter 4 of [88].

At this point, we come to a turning point in the book. The methods used in Chapters 1 to 8 have been

elementary although sometimes quite involved, but the introduction of the transition monoid of an

automaton marks the change to more advanced methods. The deeper analysis of recognisable

languages would be impossible without them.

< previous page page_189 next page >

< previous page page_190 next page >

Page 190

This page intentionally left blank.

< previous page page_190 next page >

< previous page page_191 next page >

Page 191

Chapter 9

The syntactic monoid

In the last chapter, we associated two monoids with an automaton: the transition monoid and the

monoid of representatives. The algebraic ideas described in this chapter will enable us to prove that

these two monoids are essentially the same or ‘isomorphic.’ We are not just interested in these monoids

for their own sake, they can help us to understand the properties of recognisable languages by means

of the following idea. Given a recognisable language, we can construct its minimal automaton A, which

is, as we have seen, essentially unique. The transition monoid of A might therefore be expected to have

some special significance, and it does. With any language whatsoever we can associate a monoid called

the syntactic monoid of the language. This monoid is finite precisely when the language is recognisable,

in which event the syntactic monoid is isomorphic to the transition monoid of the minimal automaton

associated with the language. With each recognisable language, therefore, we can associate a finite

monoid and this monoid can be explicitly calculated using the mininal automaton of the language.

Encoded into the algebraic structure of this monoid is information about the language.

9.1 Introduction to semigroups

In this section, I shall describe some of the elementary properties of semigroups. The first result

describes

the

fundamental property of associative binary operations.

Theorem 9.1.1

Let S be a semigroup and let . Then all bracketings of the n-fold

product x

…xnare equal

Proof The proof is by induction on the length

of the product in question. The case

=3 is just the

associative law that is given, so we may assume that

≥4. If

, x

,…, xn

are elements of our

semigroup

then one particular

< previous page page_191 next page >

< previous page page_192 next page >

Page 192

bracketing will play an important role in our proof:

We denote this by

…xn

. Let

denote any properly bracketed expression obtained by inserting

brackets into the sequence

, x

,…, xn

. Observe that the computation of such a bracketed product

involves computing

−1 products. This is because at each step we can only compute the product of

adjacent letters

xixi

+1 and the result is a single letter. Thus at each step of our calculation we reduce

the number of letters by one until there is only one letter left. However the expression may be

bracketed, the final step in the computation will be of the form

YZ,

where

and

will each have arisen

from properly bracketed expressions. In the case of

it will involve a bracketing of some sequence

,…, xr,

and for

the sequence

, xr

,…xn

for some

such that 1≤

≤

−1. Since

involves a

product of length

we may assume by the induction hypothesis that

…xr

…xr)

. Hence

by associativity,

But

…xr)Z

is a properly bracketed expression of length

−1 in

,…, xn

and so, again using the

induction hypothesis, must equal

…xn

. This produces

…xn,

as required, to show that all

possible bracketings yield the same result in the presence of associativity.

We illustrate a special case of the above proof in the example below.

Example 9.1.2 Take

=5. Then

)))

. Consider the product

((x

)(x

)

Here we have

3 and

Z=x

5. By associativity

)

. Thus

))(x

)

. But this is equal to

((x

)(x

))

again by associativity. By the induction

hypothesis

)(x

)

)),

and so

as required.

Associativity means that computing products of elements is straightforward, because we never have to

worry about how to evaluate the products as long as we maintain order. Most of the important binary

operations in mathematics are associative.1

An important consequence of associativity is that for any element

of a semigroup we may define the

th power

as the product of

with itself

times: the result is the same, however the product is

bracketed. It follows that the two

laws of exponents

apply in any semigroup:

aman

and

1But not all. The vector product of two vectors in is non-associative.

< previous page page_192 next page >

< previous page page_193 next page >

Page 193

(am)n

amn,

where

and

are any positive integers. Moreover powers of the same element

commute with one another:

aman

anam

as both products equal

. Indeed, for the case of

monoids we can extend these laws to cover exponents involving 0 using the convention that

0=1,

where 1 is the identity.

In order to show that a binary operation is associative we have in principle to check that all possible

products

(ab)c

and

a(bc)

are equal. However there are circumstances when showing that a binary

operation is associative is easy. Let (

*) be a semigroup and let be any subset. If for

every

pair

of elements a, the product then * is also a binary operation on

and we say that

closed under

*. In addition, the pair (

*) is a semigroup in its own right because the associative law

holds in

and so it must hold in

. We say that (

*) is a

subsemigroup of

(

*). Usually, we just say

that ‘

is a subsemigroup of

’ as long as the binary operation in question is clear. Now let (

*) be a

monoid with identity

. Let

be a subsemigroup of

and suppose in addition that . Then

is a

monoid in its own right and we say that

is a

submonoid

. Observe that if

is a subset of a

semigroup

it is a subsemigroup precisely when . Observe also that if

is a subsemigroup of

and

is a subsemigroup of

then

is a subsemigroup of

Example 9.1.3 Here are some examples of subsemigroups and submonoids.

(1) The set of even numbers in is a submonoid under addition. However the set of odd numbers is

not: it contains neither the identity 0 nor is it closed under addition.

(2) The set of even numbers is a subsemigroup of under multiplication because the product of two

even numbers is even. However, it is not a submonoid because the multiplicative identity of is 1,

which is not even. The set of odd numbers is a submonoid because 1 is odd and the product of two odd

numbers is odd.

(3) Let Rec

(A)

denote the set of recognisable languages over

. Then this is a submonoid of under

product of languages because if

and

are recognisable then so is

. The identity is

ε,

which is

recognisable. The set Rec

(A)

is also a monoid under union because if

and

are recognisable then so

. The identity now is , which is recognisable.

(4) The transition monoid

(A) of an automaton A with state set

is a submonoid of the full

transformation monoid

T(S)

Submonoids of

* played an important role in formulating Kleene’s Theorem as we now show. Let

a semigroup and let

. Define

< previous page page_193 next page >

< previous page page_194 next page >

Page 194

is a monoid with identity 1 then we can also define

It is easy to check that

+ is a subsemigroup of

and that if

is a monoid then

* is a submonoid of

Proposition 9.1.4

Let S be a semigroup and let X be a subset of S. Then X

is the smallest

subsemigroup of S containing X

If S is a monoid, then X

is the smallest submonoid of S containing X

Proof We prove the first case; the second case follows almost immediately. By construction,

+ is a

subsemigroup of

containing

. Suppose that

is any subsemigroup of

containing

. Then

for each

≥1. It follows that . Thus

+ is contained in every subsemigroup of

containing

Example 9.1.5 Let

be a finite alphabet. Let be any language. Then

* is the smallest

submonoid of

* containing

. This describes the purely algebraic role of the Kleene star operation.

Let

be a semigroup and

a subset of S. Then

+ is called the

subsemi-group generated by X

. A

subset

is called a

generating set

;

in this case, we say that

generated

. If a

semigroup

can be generated by a finite generating set, it is said to be

finitely generated

. We can

make the same definitions in the monoid case replacing

+ by

Examples 9.1.6 Here are some examples of finitely generated semigroups and monoids.

(1) The monoid ( , +) is finitely generated; the subset consisting of 1 alone does the trick because

every non-identity element can be obtained by adding 1 to itself the requisite number of times.

(2) Every finite semigroup

is finitely generated. For example, it is generated by

itself. However, it is

often possible to find much smaller sets to generate finite semigroups.

(3) The monoid

* is finitely generated by

itself when

is a finite alphabet.

So far, we have concentrated on the properties an individual semigroup might have, but we are also

interested in comparing different semigroups. Sets can be compared using functions, and so we shall

also use functions to compare

< previous page page_194 next page >

< previous page page_195 next page >

Page 195

semigroups. But a semigroup has more structure than the set that underlies it, so the functions we use

to compare semigroups will also have to reflect that extra structure. Let (

*) and be (

)

semigroups. A function

α: S

→

is called a

homomorphism

Suppose

is a monoid with identity

eS,

and

is a monoid with identity

. If

α(eS)

then we say

that

is a

monoid homomorphism

. Injective homomorphisms are often called

embeddings

Examples 9.1.7 Some examples of homomorphisms.

(1) Let

be an alphabet. Then

* is a monoid under concatenation. We regard as a monoid under

addition. Define a function from

* to by

This is a monoid homomorphism, because

|=|

|+|

| and |

|=0.

(2) We first met monoid homomorphisms in Section 4.2 as a means of comparing languages over

different alphabets.

(3) The set is a monoid with respect to union with identity . Likewise is a monoid with

respect to union with identity . The function defined by is a monoid

homomorphism by Lemma 7.5.2.

(4) Let A be an automaton with state set

and input alphabet

. Define by

the

effect the string

has on the set of states

. Then is a monoid homomorphism by Proposition 8.1.4.

The following properties of homomorphisms are fundamental.

Proposition 9.1.8

Let α

→

T be a homomorphism between semigroups

(i)

The image of α is a subsemigroup of T.

(ii)

If T′ is a subsemigroup of T then α

−1

(T′) is a subsemigroup of S

(iii)

Let β: T

→

U be a homomorphism between semigroups

Then βα: S

→

U is a homomorphism

These results also hold when ‘semigroup’ is replaced by ‘monoid’ and ‘homomorphism’ by ‘monoid

homomorphism.’

< previous page page_195 next page >

< previous page page_196 next page >

Page 196

Proof (i) Put

T′

=im

(α)

. Let . By assumption there exist elements such that

α(s

)

and

α(s

)

2. But

Thus

. It follows that

T′

is a subsemigroup of

The proofs of (ii) and (iii) and the monoid case are left as exercises.

Example 9.1.9 Let A=

(S, A, i, δ, T)

be an automaton. Then by Example 9.1.7(4), the function

defined by is a monoid homomorphism. The image of is the set,

which is a submonoid of

T(S)

by Proposition 9.1.8(i). It is just the transition monoid of A.

One way of comparing two semigroups is to say that despite superficial differences they are ‘essentially

the same.’

Example 9.1.10 The monoid

* under concatenation has elements that are strings of

’s. Whereas the

monoid ( , +) has elements that are natural numbers. But these two monoids are essentially the same:

the element

* corresponds to the element

of , and the product

aman

corresponds to the

sum

The mathematical way of saying that two structures of the same type are ‘essentially the same’ is

provided by the notion of ‘isomorphism.’2 We have already met the notion of isomorphism appropriate

for automata in Section 7.3. The appropriate notion for semigroups is similar. An

isomorphism of semi-

groups

is a bijective homomorphism whose inverse is a homomorphism. An

isomorphism of monoids

the same as an isomorphism of semigroups except that the homomorphisms in question are monoid

homomorphisms. If

and

are semigroups (or monoids) and there is an isomorphism from

then

we say that

S is isomorphic to T

. Isomorphic semigroups are to be regarded as essentially the same,

since they have exactly the same properties as semi-groups. See Question 11 of Exercises 9.1 for

examples. The monoid

* under concatenation and the monoid under addition are isomorphic.

We say that we know a semigroup

S up to isomorphism

if we have a semi-group

which is isomorphic

. Generally speaking, we are happy to have isomorphic copies of a semigroup, and we are not

usually worried about the nature of the elements.

2From two Greek words meaning ‘same shape.’

< previous page page_196 next page >