Alphabet
A finite set of input symbols, usually written Σ. Strings are finite sequences drawn from that alphabet.
States · transitions · languages · recognition · memory
Automata & Formal Languages
Automata theory studies deliberately simple machines so the relationship between memory, state, and recognizable patterns becomes mathematically precise. A machine consumes symbols, changes state, and decides whether the resulting string belongs to a formal language.
Anatomy of a finite automaton
A tiny amount of memory can recognize an infinite set of strings.
The machine itself is finite. The language it recognizes can contain infinitely many strings because the same transition structure can process inputs of arbitrary finite length.
States
A finite collection of abstract memory situations. The current state summarizes everything about the past that matters for future behavior.
Transition function
A rule that maps the current state and next input symbol to the machine's next state.
Start state
The state occupied before any input is consumed. It anchors every computation trace.
Accepting states
A designated subset of states. A completed input string belongs to the language exactly when the trace ends in one of them.
DFA trace lab
The machine remembers only its current state.
Choose a language and feed the deterministic finite automaton a binary string. Each symbol forces exactly one transition. When the input ends, membership is decided solely by whether the final state is accepting.
Input string
1011
start
evenaccepting1→
step 1
odd0→
step 2
odd1→
step 3
evenaccepting1→
step 4
oddevenaccept
0 → even1 → odd
oddreject
0 → odd1 → even
Regular-language toolkit
Different descriptions can encode the same recognition power.
One of automata theory's recurring moves is proving two apparently different formalisms equivalent by translating between them.
01
Regular expressions
Regular expressions and finite automata describe the same class of languages. One is a pattern notation; the other is an executable state model.
02
Nondeterminism
An NFA may branch among several next states, yet it recognizes no languages beyond those recognized by deterministic finite automata.
03
Closure
Regular languages remain regular under operations such as union, intersection, complement, concatenation, and Kleene star.
More memory, more language structure
Machine classes form a ladder of expressive power.
01Finite stateRegular languagesNo unbounded auxiliary memory. The machine chooses among finitely many remembered situations.
02Stack memoryContext-free languagesA pushdown automaton can remember an unbounded nested history using last-in, first-out access.
03General read/write memoryTuring-computable behaviorA Turing machine can revisit and rewrite an unbounded tape, supporting general algorithmic computation.