Lawson M.V. Finite Automata
Подождите немного. Документ загружается.
cover next page >
Cover
title: Finite Automata
author: Lawson, Mark V.
publisher: CRC Press
isbn10 | asin: 1584882557
print isbn13: 9781584882558
ebook isbn13: 9780203485026
language: English
subject Machine theory.
publication date: 2004
lcc: QA267.L37 2003eb
ddc: 511.3
subject: Machine theory.
cover next page >
< previous page page_a_2 next page >
Page a-2
This page intentionally left blank.
< previous page page_a_2 next page >
< previous page page_i next page >
Page i
Finite Automata
Mark V.Lawson
CHAPMAN & HALL/CRC
A CRC Press Company
Boca Raton London New York Washington, D.C.
< previous page page_i next page >
< previous page page_ii next page >
Page ii
This edition published in the Taylor & Francis e-Library, 2005.
To purchase your own copy of this or any of Taylor & Francis or Routledge’s collection of thousands of
eBooks please go to www.eBookstore.tandf.co.uk.
Library of Congress Cataloging-in-Publication Data
Lawson, Mark V.
Finite automata/Mark V.Lawson.
p. cm.
Includes bibliographical references and index.
ISBN 1-58488-255-7 (alk. paper)
1. Machine theory. I. Title.
QA267.L37 2003
511.3–dc21
2003055167
This book contains information obtained from authentic and highly regarded sources. Reprinted material
is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable
efforts have been made to publish reliable data and information, but the author and the publisher
cannot
assume responsibility for the validity of all materials or for the consequences of their use.
Neither this book nor any part may be reproduced or transmitted in any form or by any means,
electronic
or mechanical, including photocopying, microfilming, and recording, or by any information storage or
retrieval system, without prior permission in writing from the publisher.
The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for
creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC
for such copying.
Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are
used only for identification and explanation, without intent to infringe.
Visit the CRC Press Web site at www.crcpress.com
© 2004 by CRC Press LLC
No claim to original U.S. Government works
ISBN 0-203-48502-5 Master e-book ISBN
ISBN 0-203-62027-5 (OEB Format)
International Standard Book Number 1-58488-255-7 (Print Edition)
Library of Congress Card Number 2003055167
< previous page page_ii next page >
< previous page page_iii next page >
Page iii
For my teacher, T.Guérin-leTendre
Selves—goes itself;
myself it
speaks and spells,
Crying
Whát I dó is me: for that I came
.
Gerard Manley Hopkins
< previous page page_iii next page >
< previous page page_iv next page >
Page iv
This page intentionally left blank.
< previous page page_iv next page >
< previous page page_ix next page >
Page ix
Preface
Introduction
The theory of finite automata is the mathematical theory of a simple class of algorithms that are
important in computer science. Algorithms are recipes that tell us how to solve problems; the rules we
learn in school for adding, subtracting, multiplying and dividing numbers are good examples of
algorithms. Although algorithms have always been important in mathematics, mathematicians did not
spell out precisely what they were until the early decades of the twentieth century, when they started to
ask questions about the nature of mathematical proof. Perhaps motivated in part by the mechanical
devices that were used to help in arithmetical calculations, mathematicians wanted to know whether
there were mechanical ways of proving theorems. By mechanical, they did not intend to build real
machines that could prove theorems; rather they wanted to know whether it was possible
in principle
to
prove theorems mechanically. In mathematical terms, they wanted to know whether there was an
algorithm for proving the theorems of mathematics. The answer to this question obviously depended on
what was meant by the word ‘algorithm.’ Numerous definitions were suggested by different
mathematicians from various perspectives and, remarkably, they all proved to be equivalent. By the end
of the 1930s, mathematicians had a precise definition of what an algorithm was, and using this
definition they were able to show that there were problems that could not be solved by algorithmic
means. It was perhaps no accident that, as mathematicans were laying the foundations of the theory of
algorithms, engineers were constructing machines that could implement algorithms as programs.
Algorithms and programs are just two sides of the same coin.
Mathematicians were initially interested in the dividing line between what was and what was not
algorithmic. But simply knowing that a problem could be solved by means of an algorithm was not the
end of the story. Certainly, this implied you could write a program to solve the problem, but did not
imply your program would run quickly or efficiently. For this reason, two approaches to classifying
algorithms were developed. The first classified them according to their running times and is known as
complexity theory,
whereas the second classified them according to the types of memory used in
implementing them
< previous page page_ix next page >
< previous page page_v next page >
Page v
Contents
Preface ix
1 Introduction to finite automata 1
1.1 Alphabets and strings 1
1.2 Languages 5
1.3 Language operations 7
1.4 Finite automata: motivation 11
1.5 Finite automata and their languages 14
1.6 Summary of Chapter 1 21
1.7 Remarks on Chapter 1 22
2 Recognisable languages 27
2.1 Designing automata 27
2.2 Incomplete automata 29
2.3 Automata that count 33
2.4 Automata that locate patterns 37
2.5 Boolean operations 40
2.6 The Pumping Lemma 45
2.7 Summary of Chapter 2 48
2.8 Remarks on Chapter 2 49
3 Non-deterministic automata 53
3.1 Accessible automata 53
3.2 Non-deterministic automata 60
3.3 Applications 67
3.4 Trim automata 72
3.5 Grammars 76
3.6 Summary of Chapter 3 83
3.7 Remarks on Chapter 3 83
4
ε
-automata 85
4.1 Automata with
ε
-transitions 85
4.2 Applications of
ε
-automata 90
< previous page page_v next page >
< previous page page_vi next page >
Page vi
4.3 Summary of Chapter 4 95
4.4 Remarks on Chapter 4 95
5 Kleene’s Theorem 97
5.1 Regular languages 97
5.2 Kleene’s theorem: proof 103
5.3 Kleene’s theorem: algorithms 106
5.4 Language equations 114
5.5 Summary of Chapter 5 125
5.6 Remarks on Chapter 5 125
6 Local languages 127
6.1 Myhill graphs 127
6.2 Linearisation 134
6.3 Summary of Chapter 6 139
6.4 Remarks on Chapter 6 139
7 Minimal automata 141
7.1 Partitions and equivalence relations 141
7.2 The indistinguishability relation 144
7.3 Isomorphisms of automata 152
7.4 The minimal automaton 155
7.5 The method of quotients 157
7.6 Summary of Chapter 7 168
7.7 Remarks on Chapter 7 168
8 The transition monoid 171
8.1 Functions on states 171
8.2 The extended transition table 176
8.3 The Cayley table of an automaton 183
8.4 Semigroups and monoids 185
8.5 Summary of Chapter 8 188
8.6 Remarks on Chapter 8 189
9 The syntactic monoid 191
9.1 Introduction to semigroups 191
9.2 Congruences 198
9.3 The transition monoid of an automaton 207
9.4 The syntactic monoid of a language 209
9.5 Summary of Chapter 9 213
9.6 Remarks on Chapter 9 214
< previous page page_vi next page >
< previous page page_vii next page >
Page vii
10 Algebraic language theory 217
10.1 Finite semigroups 217
10.2 Recognisability by a monoid 224
10.3 Two counterexamples 231
10.4 Summary of Chapter 10 234
10.5 Remarks on Chapter 10 234
11 Star-free languages 235
11.1 Introduction 235
11.2 Groups 238
11.3 Aperiodic semigroups 249
11.4 Schützenberger’s theorem 252
11.5 An example 258
11.6 Summary of Chapter 11 261
11.7 Remarks on Chapter 11 262
12 Varieties of languages 265
12.1 Pseudovarieties and varieties 265
12.2 Equations for pseudovarieties 273
12.3 Summary of Chapter 12 276
12.4 Remarks on Chapter 12 276
A Discrete mathematics 279
A.1 Logic and proofs 279
A.2 Set theory 281
A.3 Numbers and matrices 285
A.4 Graphs 287
A.5 Functions 288
A.6 Relations 290
Bibliography 293
Index 303
< previous page page_vii next page >