What is a Finite Automaton?
The simplest model of computation with limited memory
The theory of computation begins with a question: What is a computer? Instead of dealing with real computers which are quite complicated, we use an idealized computer called a computational model.
We begin with the simplest model, called the finite state machine or finite automaton. Finite automata are good models for computers with an extremely limited amount of memory.
Despite their simplicity, finite automata are useful in many applications:
- Controllers for electronic devices (like automatic doors)
- Text processing and pattern matching
- Lexical analysis in compilers
- Protocol specification
Everyday Example
An automatic door controller is a real-world example of a finite automaton. It has two states (OPEN and CLOSED) and transitions between them based on input signals from sensors (FRONT, REAR, BOTH, or NEITHER). The door opens when someone approaches from the front and closes when no one is detected.