Lawson M.V. Finite Automata

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

< previous page page_287 next page >

Page 287

matrix multiplication is associative. If

and

are both

-matrices with entries that can be added,

then we can add

and

to form a new matrix

whose entries are defined as follows:

The set of all

-matrices with entries from some set

is denoted by

Mn(R)

A.4 Graphs

I do not use any graph theory as such, but I do use graphs to represent information. A

graph

is a

diagram consisting of points, called

vertices,

joined together by lines, called

edges

. Each edge joins

exactly two vertices. Each graph can be drawn in many ways; think of the edges as being elastic so that

they can be stretched and deformed as much as you like. We usually try to draw a graph in the simplest

possible way. When we draw graphs we are sometimes forced to make edges cross, such points are not

vertices. A pair of vertices joined by an edge are said to be

adjacent

. Two or more edges joining the

same pair of vertices are called

multiple edges

. An edge joining a vertex to itself is called a

loop

. A

graph with no loops or multiple edges is called a

simple graph

Be warned that the terminology of graph theory is not completely standardised. Furthermore, the word

‘graph’ is used with another, and quite different, meaning in mathematics: we talk about ‘graphs of

functions.’

The

degree

of a vertex is the number of edges that emerge from it. A loop at a vertex counts 2 to the

degree because we count each end of the loop. A vertex of degree zero is called an

isolated vertex

. If

is a graph, then a

subgraph

is a graph

G′,

which is obtained from

by erasing some of the edges

and some of the vertices (where ‘some’ can mean anything between ‘none’ and ‘all’). A graph that is all

in one piece is said to be

connected,

whereas one that splits into two or more pieces is said to be

disconnected

and the connected pieces that make up a graph are called its

connected components

. A

path

in a graph is a succession of edges with the property that the second vertex of each edge is the

first vertex of the next one. The

length

of a path is just the number of edges involved in the path. A

path is said to be

closed

if it begins and ends at the same vertex. A

cycle

in a graph is a closed path

with distinct vertices. Observe that a graph is connected precisely when any two vertices can be joined

by a path. A

directed graph

digraph

is a graph in which edges are replaced by arrows. A

labelled

graph whether directed or not is simply a graph of either sort with symbols labelling the edges or

arrows. Let

be a graph with set of vertices

. Then the

adjacency matrix A

is the |

|×|

|-matrix

with rows and columns labelled by the vertices defined as follows:

Aij

is the number of edges in

joining

and

. If

is a directed graph, then the entry

Aij

of its adjacency matrix is defined to be the

number of edges

from i to j

. A connected graph without cycles is called a

tree

. A tree with a

distinguished vertex is called a

rooted tree

. In a rooted tree, the vertices

< previous page page_287 next page >

< previous page page_288 next page >

Page 288

of degree one (excluding if necessary the root) are called the

leaves

. A vertex in a tree which is not a

leaf is said to be

interior

A.5 Functions

Probably the single most important definition in mathematics is that of a function. It took hundreds of

years to evolve into its current form, and at first sight may seem ‘overprecise.’ However, experience has

shown that it is the right one.

Let

and

be sets. A

function α from X to Y,

written

α: X

→

is a rule that associates with each

element

exactly one element . We write

α(x)

or . The set

is called the

domain of

and the set

is called the

codomain of α

. The element

α(x)

is called the

value of α at x

. The domain

of alpha is denoted dom

(α),

and the codomain of

is denoted cod

(α)

It is important to note that a function is determined by

three

pieces of information: the domain, the

codomain, and the rule. Change

any one

of these three pieces of information and you change the

function. It is for this reason that I said above that the definition may look ‘overprecise.’

Examples A.5.1 Some examples of functions.

(1) The function that takes as input an ordered pair of integers

(a, b)

and produces as output their sum.

The domain of this function is × , the codomain is and the rule is . We can similarly

define the subtraction function and the multiplication function with the same domains and codomains.

Notice that we write

rather than +

(a, b)

. The former is known as

infix notation

and the latter as

prefix notation

(2) The function that takes as input an ordered pair of rational numbers

(a, b)

where

≠0 and produces

as output

. The domain of this function is ×( \{0}) and the codomain is . Observe that we have

used set notation to make clear what the domain of this function is. If I had defined the domain to be

× , then I would have been obliged to assign a meaning to ‘

/0.’

(3) Let

be any set. Then the function 1

→

is defined

X(x)

for each . It is called the

identity function on X

(4) Let be a fixed element and let

→

be the function defined by

α(x)

for each . Then

is called a

constant function

Notation If

α: X

→

is a function, then the value of

at the input

is written

α(x)

. We say that the

argument x is written on the right

. However, it is just as valid to write

(x)α

. In this case, we say that

the

argument x is

< previous page page_288 next page >

< previous page page_289 next page >

Page 289

written on the left

. Now we have to choose which convention to follow. It is not an important choice,

but we should all agree. In this book, all my arguments will be written on the right except when I deal

with the full transformation monoid

T(X)

in Chapter 8 and thereafter.

Functions were traditionally defined by means of formulae; most functions in this book are defined by

means of tables: for each element of the domain

I tell you the corresponding element of the

codomain

α(x)

. Another method that is occasionally used is

recursion

. I only use this method when I

define ‘extended transition functions.’

Let

α: X

→

and

β: W

→

be two functions. Then we can define a new function

(α×β)(x, w)

(α(x), β(w))

A function

α: X

→

is sometimes called a

unary operation

. A function

α: X

→

is sometimes

called a

binary operation

. Let

be a set,

α: X

→

and

β: X

→

be functions and let . We

say that

X′

closed under α

if for each , and we say that

X′

closed under β

for each .

Let

α: X

→

and

β: Y

→

be functions. Then we can combine these two functions to form a new function

called the

composite of β and α:

the domain of is

the codomain of is

and the rule is

given by: . This operation on functions is called

composition

Functions are classified according to their properties. Particularly important are the following. Let

α:

→

be a function. Then

is said to be:

•

injective (one-to-one)

α(x)

α(x′)

implies

x′

•

surjective (onto)

if for each , there exists an such that

β(x)

•

bijective

if it is both injective and surjective.

In words: a function is injective if two different arrows cannot converge to the same element of the

codomain; a function is surjective if every element of the codomain is at the receiving end of an arrow.

It can be checked that the composition of injective functions is injective, and the composition of

surjective functions is surjective. In general, if

α: X

→

the set

is a subset of

but need not equal

. We call it the

image of α,

denoted im

(α)

. A function is surjective

precisely when its codomain is equal to its image.

Let

α: X

→

be a

bijective

function. Because

is bijective it is in particular surjective. This means that

for each

, there is

at least one

< previous page page_289 next page >

< previous page page_290 next page >

Page 290

such that

α(x)

. Because

is bijective it is in particular injective. This means that if

α(x)

α(x′)

then

x′

. It follows that for each there is

exactly one

such that

α(x)

. We may therefore

define a function

−1

: Y

→

The function

−1 is called the

inverse of α

. This function has the effect of ‘undoing’ the effect of

. By

this, I mean the following. Let

. Calculate

(x)

. This is just

−1

(α(x))

. But

maps

α(x)

and so

−1

(α(x))

. Hence

(x)

. In fact, it is not hard to show that

−1 is itself bijective and

that its inverse is

. That is

(α

−1

)

−1=

. It follows that

(y)

for each .

Let

α: X

→

be a function. If then define

then define

called the

inverse image of α

. There is a clash of notations here: we can calculate the inverse image of a

function even when it is not bijective.

The number of elements in a set

is called the

cardinality of X,

denoted by |

|. Two sets have the

same cardinality iff there is a bijection between them. A set

is said to be

countably infinite

if there is a

bijection from

to .

There is a slight generalisation of the notion of a function that we shall need. A

partial function α: X

→

from

is defined by the condition that for each there is

at most one

element . This

means that

α(x)

is either not defined

if it is defined then it has only one value. The set of elements

for which

α(x)

is defined is called the

domain of definition

. I shall denote the domain of

definition of the partial function

by dom

(α)

. If

is a partial funtion such that

α(x)

α(x′)

implies

x′

whenever

α(x)

and

α(x′)

are defined, then we say that

is a

partial injection

Let

α, β: X

→

be two partial functions. We say that

is an

extension

or that a is a restriction of

if and for all we have that

α(x)

β(x)

. We write , if

is an extension

. Let

αi,

where be a collection of functions such that . Let .

Then either

≤

. In either case,

αi(x)

αj(x)

. It follows that if we define

α: X

→

α(x)

αi(x)

then

is a well-defined partial function. We say that

is defined by taking the ‘union’ of

the functions

αi

A.6 Relations

Let

and

be sets. A

relation ρ from A to B

is simply a subset . If

we say that

is a

relation on A

. We usually write

xρy

instead of

< previous page page_290 next page >

< previous page page_291 next page >

Page 291

. If

is a relation from

and then we define

To describe a relation

we have to say which ordered pairs belong to

. If

is finite then we can

simply list them. Alternatively, we can draw a

directed graph

arrow diagram:

the vertices of the graph

are

and we draw an arrow from

and . If

then we have one

set of vertices and draw arrows between them.

Examples A.6.1 Some relations.

(1) Let

be the set of all people now alive. Let

be the relation on

defined by:

aµb

if a is the mother

. Family relations of this type are the motivation for the terminology.

(2) Let

{a, b, c, d, e, f}

and and let

This is a random example. A relation is defined as soon as the sets

and

are given and the set of

ordered pairs. A relation need not have any particular meaning, although in practice we are mainly

interested in ones that do.

(3) Let

={1, 2, 3, 4, 5} and

={1, 10, 11, 100, 101} and

This is a relation that tells us the binary representations of the first few integers.

(4) Let

= . Define

iff

divides

I will now concentrate on relations defined on a set

so that the relation in question is a subset of

Relations are classified according to their properties. The following are the most important. Let

be a

relation on a set

. Then

is said to be:

•

reflexive

if for every .

•

symmetric

if implies .

•

antisymmetric

if and imply

•

transitive

if and imply .

< previous page page_291 next page >

< previous page page_292 next page >

Page 292

A relation that is reflexive, symmetric, and transitive is called an

equivalence relation

. Equivalence

relations are discussed in more detail in Chapter 7, and play an important role thereafter.

A relation ≤ on a set

is called a

partial order (relation)

if it is reflexive,

antisymmetric,

and transitive.

Finite partial orders can be described by means of

Hasse diagrams:

these are graphs in which the

vertices are the elements of the partially ordered set, and if

≤

and there is no element

such that

≤

then we draw

lower down the page than

and connect

and

by an edge. The whole partial

order can be recovered from this diagram.

A partial order is called a

linear order

if for each pair of elements we have that either

≤

. This is true of the usual order on the integers, for example. The natural numbers have an

important order property: each non-empty subset of has a smallest element. The set of integers

with its usual order is linearly ordered, but it does not have the property that every non-empty subset

has a smallest element.

< previous page page_292 next page >

< previous page page_293 next page >

Page 293

Bibliography

[1] A.V.Aho, R.Sethi, J.D.Ullman,

Compilers: principles, techniques, and tools,

Addison-Wesley, 1986.

[2] A.V.Aho, Algorithms for finding patterns in strings, in

Algorithms and complexity, Volume A

(editor

J.van Leeuwen), Elsevier, 1992, 257–300.

[3] J.Almeida,

Finite semigroups and universal algebra,

World Scientific, 1994.

[4] D.Angluin, Inference of reversible languages,

Journal of the Association for Computing Machinery

(1982), 741–765.

[5] M.A.Arbib (editor),

Algebraic theory of machines, languages, and semigroups,

Academic Press, 1968.

[6] M.A.Arbib,

Brains, machines and mathematics,

Springer-Verlag, 1987.

[7] D.N.Arden, Delayed-logic and finite-state machines, in

Theory of computing machine design,

University of Michigan Press, Ann Arbor, Michigan, 1960, 1–35.

[8] R.A.Baeza-Yates, Searching subsequences,

Theoretical Computer Science

78 (1991), 363–376.

[9] V.Bar-Hillel, M.Perles, E.Shamir, On formal properties of simple phrase structure grammars,

Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunicationsforschung

14 (1961), 143–172.

[10] M.P.Béal, D.Perrin, Symbolic dynamics and finite automata, in

Handbook of formal languages,

Volume 2

(editors G.Rozenberg, A.Salomaa), Springer, 1997, 463–506.

[11] G.Berry, R.Sethi, From regular expressions to deterministic automata,

Theoretical Computer Science

48 (1986), 117–126.

[12] J.Berstel,

Transductions and context-free languages,

B.G.Teubner Stuttgart, 1979.

< previous page page_293 next page >

< previous page page_294 next page >

Page 294

[13] J.Berstel, J.-E.Pin, Local languages and the Berry-Sethi algorithm,

Theoretical Computer Science

155 (1996), 439–446.

[14] J.Berstel, C.Reutenauer,

Rational series and their languages,

Springer-Verlag, 1988.

[15] M.J.J.Branco, Varieties of languages, in

Semigroups, algorithms, automata and languages

(editors

G.M.S.Gomes, J.-E.Pin, P.V.Silva), World Scientific, 2002, 91–132.

[16] W.Brauer,

Automatentheorie,

B.G.Teubner, Stuttgart, 1984.

[17] A.Brüggemann-Klein, Regular expressions into finite automata,

Lecture Notes in Computer Science

583 (1992), 87–98.

[18] J.A.Brzozowski, Canonical regular expressions and minimal state graphs for definite events, in

Mathematical theory of automata,

Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn,

New York, 1962, 529–561.

[19] J.A.Brzozowski, Derivatives of regular expressions,

Journal of the Association for Computing

Machinery

11 (1964), 481–494.

[20] J.A.Brzozowski, E.J.McCluskey, Signal flow graph techniques for sequential circuit state diagrams,

IEEE Transactions on Electronic Computers,

12 (1963), 67–76.

[21] J.A.Brzozowski, I.Simon, Characterization of locally testable events,

Discrete Mathematics

4 (1973),

243–271.

[22] J.R.Büchi,

Finite automata, their algebras and grammars

(editor D.Siefkes), Springer-Verlag, 1989.

[23] J.Carroll, D.Long,

Theory of finite automata,

Prentice-Hall International, 1989.

[24] J.-M.Champarnaud, J.-E.Pin, A maxmin problem on finite automata,

Discrete Applied Mathematics

23 (1989), 91–96.

[25] C.Choffrut, Minimizing subsequential transducers: a survey,

Theoretical Computer Science

292

(2003), 131–143.

[26] S.Choi, D.T.Huynh, Finite automaton aperiodicity is PSPACE-complete,

Theoretical Computer

Science

88 (1991), 99–116.

[27] N.Chomsky, Three models for the description of languages,

IRE Transactions of Information Theory

2 (1956), 113–124.

[28] N.Chomsky,

Syntactic structures,

Mouton, 1975.

< previous page page_294 next page >

< previous page page_295 next page >

Page 295

[29] N.Chomsky, G.A.Miller, Finite state languages,

Information and Control

1 (1958), 91–112.

[30] N.Chomsky, M.P.Schützenberger, The algebraic theory of context-free languages, in

Computer

programming and formal systems

(editors P.Brafford, E.Hirschberg), North-Holland, Amsterdam, 1963,

118–161.

[31] P.S.Churchland,

Neurophilosophy,

The MIT Press, 1990.

[32] A.H.Clifford, G.B.Preston,

The algebraic theory of semigroups,

vol. I, American Mathematical

Society, Providence, R.I., 1961.

[33] A.H.Clifford, G.B.Preston,

The algebraic theory of semigroups,

vol. II, American Mathematical

Society, Providence, R.I., 1967.

[34] D.I.A.Cohen,

Introduction to computer theory,

Second Edition, John Wiley and Sons, 1997.

[35] J.H.Conway,

Regular algebra and finite machines,

Chapman and Hall, 1971.

[36] T.H.Cormen, C.E.Leiserson, R.L.Rivest,

Introduction to algorithms,

The MIT Press, 1990.

[37] M.Chrochemore, C.Hancart, Automata for matching patterns, in

Handbook of formal languages,

Volume 2

(editors G.Rozenberg, A.Salomaa), Springer, 1997, 399–462.

[38] K.Culik II, J.Kari, Digital images and formal languages, in

Handbook of formal languages, Volume 3

(editors G.Rozenberg, A.Salomaa), Springer, 1997, 599–616.

[39] S.Eilenberg,

Automata, languages and machines, Volume A,

Academic Press, 1974.

[40] S.Eilenberg,

Automata, languages and machines, Volume B,

Academic Press, 1976.

[41] S.Eilenberg, M.P.Schützenberger, On pseudovarieties,

Advances in Mathematics

19 (1976), 413–

418.

[42] T.S.Eliot,

Four quartets,

Faber Paperbacks, 1976.

[43] D.B.A.Epstein, J.W.Cannon, D.F.Holt, S.V.F.Levy, M.S.Paterson, W.P.Thurston,

Word processing in

groups,

Jones and Bartlett, 1992.

[44] R.W.Floyd, R.Beigel,

The language of machines,

Computer Science Press, 1994.

< previous page page_295 next page >

< previous page page_296 next page >

Page 296

[45] J.Fountain (editor),

Semigroups, formal languages and groups,

Kluwer Academic Publishers, 1995.

[46] J.B.Fraleigh,

A first course in abstract algebra,

Fifth Edition, Addison-Wesley, 1994.

[47] J.E.F.Friedl,

Mastering regular expressions,

Second Edition, O’Reilly, 2002.

[48] R.Fröberg, C.Gottlieb, R.Häggkvist, On numerical semigroups,

Semigroup Forum

35 (1987), 63–83.

[49] W.H.Gardner,

Poems and prose of Gerard Manley Hopkins,

Penguin Books, 1978.

[50] F.Gécseg, I.Peák,

Algebraic theory of automata,

Akadémiai Kiadó, Budapest, 1972.

[51] R.H.Gilman, Formal languages and infinite groups,

DIMACS Series in Discrete Mathematics and

Theoretical Computer Science

25 (1996), 27–51.

[52] D.Giammarresi, A.Restivo, Two-dimensional languages, in

Handbook of formal languages, Volume 3

(editors G.Rozenberg, A.Salomaa), Springer, 1997, 215–267.

[53] S.Ginsburg, G.F.Rose, Operations which preserve definability in languages,

Journal of the

Association for Computing Machinery

10 (1963), 175–195.

[54] A.Ginzburg,

Algebraic theory of automata,

Academic Press, 1968.

[55] V.M.Glushkov, The abstract theory of automata,

Russian Mathematical Surveys

16 (1961), 1–53.

[56] G.M.S. Gomes, J.-E.Pin, P.V.Silva,

Semigroups, algorithms, automata and languages,

World

Scientific, 2002.

[57] R.I.Grogorchuk, V.V.Nekrashevich, V.I.Sushchanskii, Automata, dynamical systems, and groups,

Proceedings of the Steklov Institute of Mathematics

231 (2000), 128–203.

[58] F.von Haeseler,

Automatic sequences,

Walter de Gruyter, 2003.

[59] P.R.Halmos,

Naive set theory,

Springer-Verlag, 2001.

[60] J.Hartmanis, R.E.Stearns, Sets of numbers defined by finite automata,

American Mathematical

Monthly

74 (1967), 539–542.

[61] P.M.Higgins, A proof of Simon’s theorem on piecewise testable languages,

Theoretical Computer

Science

178 (1997), 257–264.

< previous page page_296 next page >