Cover
Preface
Contents
Index
Glossary
Models
Rogues
| |
Finite State Automata
(Contents)
-
Huh???
Computing with Finite State Automata
|
Understanding how finite state automata can be used to
solve problems |
|
Real-world problems for which finite state automata are
used |
|
Finite state automata as pattern checkers (recognizers) |
|
Exercises
|
Problems that Cannot be Solved with Finite State Automata
|
Limitations on the power of finite state automata |
|
Examples of problems not solvable by finite state
automata |
|
A way to tell whether a problem is solvable by a finite
state automaton or not (the pumping lemma) |
|
Exercise 1 |
|
Exercise 2
|
Implementing a Finite State Automaton as a Program
Nondeterministic Finite State Automata
|
What is nondeterminism? |
|
Animated examples |
|
Why in the world would we want a nondeterministic finite
state automaton? |
| A real world example |
|
How to show that nondeterministic and deterministic
finite state automata can solve the exactly the same set of problems |
|
Exercises
|
Regular Expressions and Finite State Automata
|
What are regular expressions? |
|
Why bother? |
|
Animated examples |
|
Animated exercises |
|
How to see that regular expressions can be used to
describe exactly the set of problems that finite state automata can
solve |
|
Why different approaches to the same topic are important |
|
Exercises
|
Regular Grammars and Finite State Automata
|
What does grammar have to do with the theory of
computing? |
|
What makes a grammar regular? |
|
Animated examples |
|
Animated exercises |
|
How to show that regular grammars can produce exactly
the same sets that finite state automata can recognize |
|
Exercises |
|