Finite Automata — Mathematics Knowledge System

Overview

A finite automaton is the simplest formal model of computation: a machine with a finite set of states that reads an input symbol at a time and moves between states according to fixed rules, accepting or rejecting the input based on which state it ends in. Despite their simplicity, finite automata exactly capture the 'regular languages' — the class of patterns matched by regular expressions — and form the theoretical foundation of lexical analysis in compilers, text search, and protocol design.

Intuition

Think of a vending machine that only accepts a specific coin sequence. It has a small number of 'states' (how much money inserted so far), and each coin moves it to a new state. If it ends in the 'dispense' state after the input stops, it accepts; otherwise it rejects. A finite automaton generalizes this: any pattern-matching task where the answer only depends on a fixed, finite amount of 'memory' about what's been seen so far can be modeled this way.

Interactive Graph

Formal Definition

Definition

A deterministic finite automaton (DFA) is a 5-tuple:

M = (Q, \Sigma, \delta, q_0, F)

Definition

\delta: Q \times \Sigma \to Q

The transition function: current state × input symbol → next state

Notation

Notation	Meaning
$Q$	The finite set of states
$\Sigma$	The input alphabet (finite set of symbols)
$\delta$	The transition function
$q_0$	The start state
$F \subseteq Q$	The set of accepting (final) states

Derivation

Building a DFA that accepts binary strings with an even number of 1s: two states track the parity of 1s seen so far.

Q = \{q_{\text{even}}, q_{\text{odd}}\}, \quad q_0 = q_{\text{even}}, \quad F = \{q_{\text{even}}\}

\delta(q_{\text{even}}, 1) = q_{\text{odd}}, \quad \delta(q_{\text{odd}}, 1) = q_{\text{even}}, \quad \delta(q, 0) = q

Reading a 1 flips parity; reading a 0 does nothing

Theorems

Theorem 1: NFA-DFA equivalence

\text{For every nondeterministic finite automaton (NFA), there exists a DFA that accepts the exact same language (via the subset construction).}

Theorem 2: Kleene's theorem

\text{A language is recognized by some finite automaton if and only if it is described by some regular expression.}

Applications

Lexical analyzers in compilers use DFAs to tokenize source code (identifying keywords, numbers, operators).

Worked Examples

Two states: 'last symbol was 0' (start, non-accepting) and 'last symbol was 1' (accepting).
$\delta(q_0, 1) = q_1,\ \delta(q_1, 1)=q_1,\ \delta(q_0,0)=q_0,\ \delta(q_1,0)=q_0$

Answer: A 2-state DFA with F = {q₁}

Practice Problems

Difficulty 5/10

How many states does the minimal DFA need to recognize binary strings divisible by 3 (as a binary number)?

Difficulty 4/10

A subway turnstile has two states: Locked and Unlocked. A coin unlocks it; pushing through re-locks it. Model this as a finite automaton — how many states and what are the transitions?

Difficulty 6/10

Every compiler's lexical analyzer (tokenizer) and every regex engine is built on finite automata. Explain why a DFA can scan input text in time linear in its length.

Difficulty 6/10

Which task is IMPOSSIBLE for a finite automaton (a regular language limitation)?

Recognizing strings that end in '01'Recognizing balanced/matched parentheses of arbitrary depthRecognizing binary numbers divisible by 3Recognizing strings of even length

Common Mistakes

Common Mistake

Assuming nondeterministic automata (NFAs) are strictly more powerful than DFAs.

NFAs and DFAs recognize exactly the same class of languages (regular languages) — NFAs can just be more concise to describe; any NFA can be converted to an equivalent DFA (possibly with exponentially more states).

Quiz

Historical Background

Finite automata were formalized in the 1940s-50s by Warren McCulloch and Walter Pitts (modeling neurons) and later by Stephen Kleene, who proved their equivalence to regular expressions in 1956. Michael Rabin and Dana Scott's 1959 paper on nondeterministic automata (winning them the 1976 Turing Award) showed nondeterministic and deterministic finite automata recognize exactly the same languages — a foundational result in computer science.

1943
McCulloch and Pitts model neural networks with finite-state machines
Warren McCulloch, Walter Pitts
1956
Stephen Kleene proves finite automata are equivalent to regular expressions
Stephen Kleene
1959
Rabin and Scott formalize nondeterministic finite automata (NFA)
Michael Rabin, Dana Scott

Summary

A finite automaton is a state machine with a finite number of states, transitioning on input symbols.
Formally a 5-tuple (Q, Σ, δ, q₀, F).
DFAs and NFAs recognize exactly the regular languages (Kleene's theorem).
Finite automata underlie lexical analysis, regex engines, and protocol verification.

References

WebsiteWikipedia — Finite-state machine