Lawson M.V. Finite Automata

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

< previous page page_117 next page >

Page 117

Arden’s theorem tells us how to solve one equation in one unknown. We shall show later how it can be

used to solve

equations in

unknowns. First we need to define what we mean by ‘right linear

equations in many unknowns.’

Let

be an alphabet. A

set of n right linear equations in n unknowns Xi,

where

=1,…,

is a set of

equations of the form,

where the

Cij

and

are languages over

. These equations can be put into matrix form, which is

sometimes more convenient: let X be the

×1 matrix,

and let R be the

×1 matrix,

and finally let C be the

matrix,

Then our set of

equations in

unknowns takes the form

Systems of equations such as this can be constructed from any automaton. Let

be an automaton. For each

=1,…,

define

that is,

is the language recognised by the automaton

(S, A, si, δ, T)

. Observe that

(A). The

languages

,…, Xn

are the principal actors in the following algorithm.

< previous page page_117 next page >

< previous page page_118 next page >

Page 118

Algorithm 5.4.3 (Equations associated with a finite automaton) Let

be a finite automaton. Let C be the

-matrix defined as follows: C

i,j

the union of all the such

that

. Let R be the

×1-matrix defined as follows:

The

equations associated with

A are X=CX+R.

Notice that the matrix

is related to the adjacency matrix of the underlying directed graph: in the

adjacency matrix the entry in the

th row and

th column would give the number of arrows from

whereas the entry

Cij

is the union of the labels of the transitions from

. Before we justify our

algorithm we give an example.

Example 5.4.4 We return to our first example of an automaton: Example 1.5.1.

This machine has two states, and so there will be two unknowns:

The language accepted by this machine is

. The matrix of coefficients C derived from this automaton is

The matrix R encoding terminal and non-terminal states is

Thus the equations associated with the automaton in matrix form are

That is,

< previous page page_118 next page >

< previous page page_119 next page >

Page 119

We now justify Algorithm 5.4.3.

Theorem 5.4.5

Let

be an automaton. For each i

=1,…,

n define

(i)

Let si be a non-terminal state. Suppose that , where j

=1,…,

. Then

(ii)

Let si be a terminal state. Suppose that , where j

=1,…,

. Then

Proof (i)

Let

. Then by definition, . Since

is not a terminal state, the string

has at

least one symbol. Thus we can write

where and . We must have

for some

=1…

. Thus

It follows that

and so . We have therefore shown that

To prove the reverse inclusion, let

. Say . Then

ajy

where . By

definition . Thus

Hence . This proves the result.

(ii) The proof of this case is the same as (i), except that if

is terminal, the empty string will take

a terminal state, namely

itself.

Thus from a deterministic automaton with

states, we obtain

right linear equations in

unknowns.

One of these unknowns is the language recognised by the automaton. The algorithm for solving these

equations makes repeated use of Arden’s Theorem. The condition we impose on the coefficients of the

matrix is one that automatically holds for the equations arising from deterministic automata.

< previous page page_119 next page >

< previous page page_120 next page >

Page 120

Algorithm 5.4.6 (Solving systems of right linear equations) Let

be a set of

right linear equations in

unknowns

,…, Xn

. Assume in addition that no entry of C

contains

. The algorithm computes the value of

1, and then the values of

,…, Xn

in turn.

The algorithm works iteratively to successively remove each unknown

Xn, Xn

−1

,…, X

2. Thus at the end

of the first stage, we have

−1 equations in the unknowns

…, Xn

−1

;

at the end of the second stage,

we have

−2 equations in the unknowns

…, Xn

−2

;

and so forth, until at the end of the final stage we

have one equation in the unknown

1. Once we have one equation in

1 we can apply Arden’s

Theorem to obtain an explicit description of

1. The values of

,…, Xn

can then be calculated in turn

by back substitution.

The key procedure is as follows:

• The last equation in the system has the form

• Rearrange this equation to obtain

• Apply Arden’s Theorem to express

in terms of

,…, Xn

−1

• Substitute this value for

into the preceding

−1 equations, to obtain

−1 equations in

−1

unknowns, the coefficient matrix of which has the property that no entry contains

Before we justify this algorithm we work through two examples.

Example 5.4.7 We return to the two equations we obtained from Example 5.4.4:

(5.1)

(5.2)

To solve these equations using Algorithm 5.4.6, we take the last equation first:

and rearrange it:

< previous page page_120 next page >

< previous page page_121 next page >

Page 121

We now apply Arden’s Theorem to express

in terms of

We now substitute this expression for

into equation (5.1) to obtain

which we rearrange to obtain

By Arden’s Theorem we obtain the following explicit description of

This is the language recognised by our automaton. We originally found that the language recognised by

this automaton was (

. It follows that

In our next example, we consider three equations in three unknowns.

Example 5.4.8 Consider the following three equations in

X, Y,

and

below:

(5.3)

(5.4)

(5.5)

Our aim is to find an explicit expression for

. We take the last equation first:

and rearrange it:

Apply Arden’s Theorem to obtain a description of

in terms of

and

Substitute this expression for

into equations (5.3) and (5.4):

(5.6)

(5.7)

Rearrange these equations to obtain

(5.8)

(5.9)

< previous page page_121 next page >

< previous page page_122 next page >

Page 122

We started with three equations and three unknowns

X, Y, Z;

we now have two equations in two

unknowns

X, Y

together with an expression for

in terms of

and

. We can apply our procedure

again to these two equations to obtain one equation in one unknown

and two expressions: one of

in terms of

and one of

in terms of

and

We now justify Algorithm 5.4.6.

Theorem 5.4.9

Let

X=CX+R

be a set of n right linear equations in n unknowns

Assume in addition

that no entry of

contains ε

Then the equations have a unique solution. If, in addition, all the entries

and

are regular, then the solution is regular

Proof Before we present the formal proof of the first part of the theorem, we describe the idea that lies

behind it. This is just a re-iteration of Algorithm 5.4.6. Let X=CX+R be a set of

right linear equations

unknowns such that each entry of C does not contain

. The last equation in the system has the

form

By rearranging this equation, we obtain

solutions to

,…, Xn

−1 existed,

then

we could use Arden’s theorem to find

Xn:

If we substitute this value for

into the preceding

−1 equations, we obtain

−1 equations in

−1

unknowns, whose coefficient matrix has the property that no entry contains

. Iterating this procedure,

we would eventually obtain one equation in

1. By Arden’s theorem we could solve the equation

explicitly. The values of

,…, Xn

could then be explicitly calculated in turn. We now have to make this

idea precise.

Let

P(n)

denote the following statement:

“Every set of

right linear equations in

unknowns has a unique solution if the coefficient matrix has

the property that no entry contains the empty string.”

The statement

(1) is true by Theorem 5.4.2(iii). As our induction hypothesis, assume that

(

−1) is

true; we shall prove that

P(n)

is true. Let X=CX+R be a set of

right linear equations in

unknowns

such that each entry of C does not contain

. We associate with this system a set of

−1 equations in

−1 unknowns as follows: let

< previous page page_122 next page >

< previous page page_123 next page >

Page 123

and

and finally let

Observe that no coefficient of C′ contains

. By the induction hypothesis, the system X′=C′X′+R′ has a

unique solution:

Define

We claim that

is a solution to X=CX+R. First we calculate the

th row of the right-hand side,

for 1≤

≤

−1. This is achieved by replacing

and then collecting together like terms. By using the

th. row of the equation X=CX+R, it is easy to

check that we obtain

Li,

as required. It remains to calculate

As before, replace

and then collect together like terms. The coefficient of

which is equal to

Consequently we get

Ln,

as required.

We have proved that the system X=CX+R has at least one solution. It remains to prove that it has

exactly one solution. Suppose that there were two solutions:

,…, Ln

and

,…, Mn

. Both

,…, Ln

−1

and

,…, Mn

−1 are solutions to X′=C′X′+R′ and so by the induction hypothesis

< previous page page_123 next page >

< previous page page_124 next page >

Page 124

We can now use the idea introduced at the beginning of the proof. Consider the final equation:

We can bracket the terms in the following way:

By assumption, and

,…, Xn

−1=

−1. Thus by Arden’s theorem the equation has the

unique solution,

and so

Mn,

as required.

The second part of the theorem follows immediately because we only use regular operators to calculate

the solution.

Exercises 5.4

1. For each automaton A below, write down the corresponding set of language equations, solve them,

and so find a regular expression for the language recognised by A.

(i)

(ii)

(iii)

(iv)

(v)

< previous page page_124 next page >

< previous page page_125 next page >

Page 125

(vi)

2. For each of the following sets of language equations write down the automaton that produced the

equations (assume that

corresponds to the initial state). Also find a regular expression for

in each

case.

(i)

)

ε, Y

)

Z, Z

)

(ii)

bY, Y

bZ, Z

(iii)

aZ, Y

ε, Z

5.5 Summary of Chapter 5

•

Regular expressions:

Let

be an alphabet. A regular expression is constructed from the symbols

ε,

and

where , together with the symbols +, ·, and * and left and right brackets according to the

following rules:

ε, ,

and

are regular expressions, and if

and

are regular expressions so are (

and

)

•

Regular languages:

Every regular expression

describes a language

L(r)

. A language is regular if it can

be described by a regular expression.

•

Kleene’s theorem:

A language is recognisable if and only if it is regular. The proof of this theorem can

be made algorithmic: there is an algorithm that constructs an

-automaton A from each regular

expression

such that

(A)=

L(r);

there is also an algorithm that constructs a regular expression

from

an automaton A by graphical means such that

L(r)

(A). There is another algorithm that associates

with each automaton A with

states

right linear equations in

unknowns. These equations may be

solved to find a regular expression

such that

(A)=

L(r)

5.6 Remarks on Chapter 5

Both [66] and [75] give fuller accounts of regular expressions than I have done at about the same level

as this book. Kleene’s Theorem was first stated and proved in [74]. My proof that the language

recognised by a non-deterministic automaton is regular is taken from [51]. The two algorithms of

Section 5.3 are due to McNaughton and Yamada [86] and Brzozowski and McCluskey [20], respectively.

I learnt about the second algorithm from [16]. The theory of language equations is due to Arden [7].

< previous page page_125 next page >

< previous page page_126 next page >

Page 126

Regular expressions form a precise notation for describing languages with the added advantage over

automata that they can be written as strings on the line. Furthermore, they can be implemented: for

example, by means of the egrep command in UNIX (see Section 4.3 of [44], or Section 3.3 of [66] for

example). A detailed account of how regular expressions can be used in solving practical programming

problems may be found in [47]. See also the bibliographic notes on pages 157 and 158 of [1]. Finite

automata and regular expressions are also useful in information extraction. See [72] pages 577–583.

The problem of converting a regular expression into an automaton is an important one. In this book, we

describe two further such algorithms: one in Chapter 6 via linearisation and local automata due to Berry

and Sethi [11]; and the other is the ‘Method of Quotients’ described in Chapter 7 due to Brzozowski

[19]. More about algorithms to convert automata into regular expressions can be found in [17], and

further references in [13].

< previous page page_126 next page >