.

0 (hodnocen0 x )

BK

Boca Raton : Chapman & Hall, c2004

xii,307 s.

ISBN 1-58488-255-7 (váz.)

Obsahuje předmluvu, rejstřk, údaje o autorovi

Bibliografie: s. 293-301

Automaty konečné - pojednání

000030440

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 // 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 // Contents 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