Theory → Automata Theory
Finite Automaton
An abstract machine with a finite number of states used to recognize regular languages.
Motivation
Finite automata solve the problem of recognizing simple patterns with a limited amount of memory.
Where it fits
They belong to automata theory and formal languages. They explain regular languages and appear in lexers, regex engines, and protocol state machines.
Subconcepts
DFA
A deterministic finite automaton has exactly one next state for each state and input symbol.
NFA
A nondeterministic finite automaton can have multiple possible transitions, but recognizes the same class of languages as a DFA.
Common mistakes
- Thinking NFAs are more powerful than DFAs in terms of recognized languages.
- Treating automata as purely academic, even though they appear in parsing and validation tools.