Finite State Automata
(Contents)
-
Huh???
 | |
|
What do the terms "finite" and "state" mean in the name "finite state automaton?" |
| |
| |
| |
| |
|
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
|
Converting a finite state automaton to a program |
| |
|
Exercises |
Nondeterministic Finite State Automata
| |
|
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? |
| |
|
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 |
|
How to show that regular grammars can produce exactly the same sets that finite state automata can recognize |
|
Exercises |
