State machines are models of computation. They have a finite number of states, and can be in exactly one at a time. They can undergo a transition between states in response to certain events.
The logic of a microwave oven is an example of a state machine.
A microwave oven keeps track of its current state to determine what action to take upon any event.
It does not start running when the door is open, and if the door is open while it is running, it stops.
Depicted is the state transition diagram of a microwave oven.
Finite state machines (FSMs) are models of computation.
They take as input a word with respect to some alphabet and transition between a finite number of states as they read the symbols of the word from left to right.
The transition taken depends only on the current state and the next input symbol.
Recognizers produce a binary output: either accepted or rejected.
They define a language of all words they accept.
Classifiers are a generalization of recognizers.
They produce an n-ary output that classifies the input word.
Transducers produce an output word.
They can be thought of as translators from one language to another.
Languages are among the most important concepts studied in theory of computation.
We need to be able to define them more rigorously than we can with natural language alone.
Recognizers are of particular interest because they define languages.
All recognizers are made up of the following components:
Don't let this notation scare you!
Recognizers have two representations:
| Deterministic Finite Automata | Nondeterministic Finite Automata |
|---|---|
| May only be in one state at a time. | May be in any number of states concurrently. |
| Allows for ε transition | Does not allow ε transition |
The two types of recognizers are discussed more deeply in the subsequent pages.