Lawson M.V. Finite Automata

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

< previous page page_57 next page >

Page 57

The following construction omits the calculation of

whenever

is a repeat, which means that the

whole tree is not constructed; in addition, it also enables us to detect when all accessible states have

been found without having to count.

Algorithm 3.1.4 (Transition tree of an automaton) Let A be an automaton. The

transition tree

A is constructed inductively in the following way. We assume that a linear ordering of

is specified at

the outset so we can refer meaningfully to ‘the elements of

in turn’:

(1) The root of the tree is

0 and we put

}

(2) Assume that

has been constructed; vertices in

will have been labelled either ‘closed’ or ‘non-

closed.’ The meaning of these two terms will be made clear below. We now show how to construct

+1.

(3) For each non-closed leaf

and for each in turn construct an arrow from

labelled

if, in addition,

is a repeat of any state that has already been constructed, then we say it is

closed

and mark it with a×.

(4) The algorithm terminates when all leaves are closed.

We have to prove that the algorithm above is what we want.

Proposition 3.1.5

Let

Then there exists an m

≤

n such that every leaf in Tmis closed, and Sais

just the set of vertices in Tm

Proof Let

and let be the smallest string in the tree order such that

0·

. Then

first

appears as a vertex in the tree

T|x|

. By Lemma 3.1.3, the latest an accessible state can appear for the

first time is in

−1. Thus at worst all states in

are closed.

The transition tree not only tells us the accessible states of A but can also be used to construct A

follows: erase the ×’s and glue leaves to interior vertices with the same label. The diagram that results

is the transition diagram of A

. All of this is best illustrated by means of an example.

Example 3.1.6 Consider the automaton A pictured below:

< previous page page_57 next page >

< previous page page_58 next page >

Page 58

We shall step through the algorithm for constructing the transition tree of A and so construct A

. Of

course, it is easy to construct A

directly in this case, but it is the algorithm we wish to illustrate.

The tree

0 is just

The tree

1 is

The tree

2 is

2 is the transition tree because every leaf is closed. This tree can be transformed into an automaton as

follows. Erase all ×’s, and mark initial and terminal states. This gives us the following:

< previous page page_58 next page >

< previous page page_59 next page >

Page 59

Now glue the leaves to the interior vertices labelling the same state. We obtain the following

automaton:

This is the automaton A

Exercises 3.1

1. Construct transition trees for the automata below.

(i)

(ii)

(iii)

< previous page page_59 next page >

< previous page page_60 next page >

Page 60

3.2 Non-deterministic automata

Deterministic automata are intended to be models of real machines. The non-deterministic automata we

introduce in this section should be regarded as tools helpful in designing deterministic automata rather

than as models of real-life machines. To motivate the definition of non-deterministic automata, we shall

consider a simple problem.

Let

be an alphabet. If

…an

where

then the

reverse of x,

denoted rev

(x),

is the string

an…a

1. We define rev

(ε)

. Clearly, rev(rev

(x)

and rev

(xy)

=rev

(y)

rev

(x)

. If

is a language then

the

reverse of L,

denoted by rev

(L),

is the language

Consider now the following question: if

is recognisable, then is rev

(L)

recognisable? To see what might

be involved in answering this problem, we consider an example.

Example 3.2.1 Let

)(

)*, the language of all strings of

’s and

’s that begin with a

double letter. This language is recognised by the following automaton:

In this case, rev

(L)

is the language of all strings of

’s and

’s that

end

with a double letter. In order to

construct an automaton to recognise this language, it is tempting to modify the above automaton in the

following way: reverse all the transitions, and interchange initial and terminal states, like this:

< previous page page_60 next page >

< previous page page_61 next page >

Page 61

This diagram violates the rules for the transition diagram of a complete, deterministic finite-state

automaton in two fundamental ways: there is more than one initial state, and there are forbidden

configurations. However, if we put to one side these fatal problems, we do notice an interesting

property of this diagram: the strings that label paths in the diagram, which begin at one of the initial

states and conclude at the terminal state, form precisely the language rev

(L):

those strings that

end

in a

double letter.

This diagram is in fact an example of a non-deterministic automaton. After giving the formal definition

below, we shall prove that every non-deterministic automaton can be converted into a deterministic

automaton recognising the same language. An immediate application of this result can be obtained by

generalising the example above; we will therefore be able to prove that the reverse of a recognisable

language is also recognisable.

Recall that if

is a set, then is the power set of

the set of all subsets of

. The set

contains both and

as elements. A

non-deterministic automaton

A is determined by five pieces of

information:

where

is a finite set of states,

is the input alphabet,

is a set of initial states, is the

transition function, and

is a set of terminal states.

In addition to allowing any number of initial states, the key feature of this definition is that

δ(s, a)

now a subset of

(possibly empty!). We can draw transition diagrams and transition tables just as we

did for deterministic machines. The transition table of the machine we constructed in Example 3.2.1 is

as follows:

It now remains to define the analogue of the ‘extended transition function.’ For each string

and

state we want to know

the set of all possible states

that can be reached by paths starting at

and labelled by

. The formal definition is as follows and, as in the deterministic case, the function being

defined exists and is unique. The function

* is the unique function from

* to satisfying the

following three conditions where

and

(ETF1)

(s, ε)

{s}

< previous page page_61 next page >

< previous page page_62 next page >

Page 62

(ETF2)

(s, a)

δ(s, a)

(ETF3)

Condition (ETF3) needs a little explaining. Suppose that

δ(s, a)

,…, qn}

. Then condition (ETF3)

means

Notation We shall usually write

rather than

(s, x),

but it is important to remember that

is a

set

in this case.

Let us check that this definition captures what we intended.

Lemma 3.2.2

Let Then if and only if there exist states q

,…, qn

t such that

and for i

=2,…,

Proof The condition simply says that if and only if the string

labels some path in A starting at

and ending at

. Observe that if and only if for some state . By

applying this observation repeatedly, starting with

…an,

we obtain the desired result.

The language

(A) is defined to be

That is, the language recognised by a non-deterministic automaton consists of all strings that label

paths starting at one of the initial states and ending at one of the terminal states.

It might be thought that because there is a degree of choice available, non-deterministic automata

might be more powerful than deterministic automata, meaning that non-deterministic automata might

be able to recognise languages that deterministic automata could not. In fact, this is not so. To prove

this, we shall make use of the following construction. Let A=

(S, A, I, δ, T)

be a non-deterministic

automaton. We construct a deterministic automaton A

= (

Sd, A, id,

Δ,

) as follows:

•

the set of states is labelled by the subsets of

•

the initial state is labelled by the subset consisting of all the initial states.

•

the terminal states are labelled by the subsets that contain at least one

terminal state.

< previous page page_62 next page >

< previous page page_63 next page >

Page 63

• For and define

this means that the subset Δ

(Q, a)

consists of all states in

that can be reached from states in

following a transition labelled by

It is clear that A

is a complete, deterministic, finite automaton.

Theorem 3.2.3 (Subset construction)

Let

be a non-deterministic automaton

Then

dis a

deterministic automaton such that L

(A).

Proof The main plank of the proof will be to relate the extended transition function Δ* in the

deterministic machine A

to the extended transition function

* in the non-deterministic machine A. We

shall prove that for any

and we have that

(3.1)

This is most naturally proved by induction on the length of the string

For the base step, we prove the theorem holds when

. By the definition of Δ, we have that Δ*

(Q,

ε)

whereas by the definition of

* we have that .

For the induction hypothesis, assume that (3.1) holds for all strings

satisfying |

. Consider

now the string

where |

+1. We can write

where and and |

. From the

definition of Δ* we have

Put

Q′

=Δ

(Q, a)

. Then

by the induction hypothesis. From the definitions of

Q′

and Δ we have that

By the definition of

* we have that

This proves the claim.

< previous page page_63 next page >

< previous page page_64 next page >

Page 64

We can now easily prove that

(A)=

). By definition,

From the definition of the terminal states in A

this is equivalent to

We now use equation (3.1) to obtain

This is of course equivalent to

The automaton A

is called the

determinised

version of A.

Notation Let A be a non-deterministic automaton with input alphabet

. Let

be a set of states and

. We denote by

the set of all states that can be reached by starting in

and following

transitions labelled only by

. In other words, Δ

(Q, a)

in the above theorem, We define

Example 3.2.4 Consider the following non-deterministic automaton A:

The corresponding deterministic automaton constructed according to the subset construction has 4

states labelled ,

{p}, {q},

and

{p, q};

the initial state is the state labelled

{p, q}

because this is the set

of initial states of A; the terminal states are

{q}

and

{p, q}

because these are the only subsets of

{p, q}

that contain terminal states of A; the transitions are calculated according to the definition of Δ. Thus A

is the automaton:

Observe that the state labelled by the empty set is a sink state, as it always must be.

< previous page page_64 next page >

< previous page page_65 next page >

Page 65

The obvious drawback of the subset construction is the huge increase in the number of states in passing

from A to A

. Indeed, if A has

states, then A

will have 2

states. This is sometimes unavoidable as

we ask you to show in Exercises 3.2, but often the machine A

will contain many inaccessible states.

There is an easy way of avoiding this: construct the transition tree of A

directly from A and so

construct (A

)

. This is done as follows.

Algorithm 3.2.5 (Accessible subset construction) The input to this algorithm is a non-deterministic

automaton A=

(S, A, I, δ, T)

and the output is A

da,

an accessible deterministic automaton recognising

(A). The procedure is to construct the transition tree of A

directly from A. The root of the tree is the

set

. Apply the algorithm for the transition tree by constructing as vertices

for each non-closed

vertex

and input letter

We show how this algorithm works by applying it to the non-deterministic automaton constructed in

Example 3.2.1.

Example 3.2.6 The root of the tree is labelled {4, 6}, the

set

of initial states of the non-deterministic

automaton. The next step in the algorithm yields the tree:

Continuing with the algorithm, we obtain the transition tree of (A

)

da:

< previous page page_65 next page >

< previous page page_66 next page >

Page 66

Finally, we obtain the automaton A

pictured below:

Exercises 3.2

1. Apply the accessible subset construction to the non-deterministic automata below. Hence find

deterministic automata which recognise the same language in each case.

(i)

(ii)

(iii)

(iv)

< previous page page_66 next page >