Deterministic Finite Automata: Definition and Design
The formal definition of a DFA, how the transition function drives computation one symbol at a time, and how to design one from a plain-language description.
Finite AutomataDFA vs NFA: What's the Difference?
DFAs and NFAs accept exactly the same class of languages, but they model computation differently: one path at a time versus every path at once.
Finite AutomataRegular Expressions to NFA: Thompson's Construction
Thompson's construction builds an NFA out of small, composable pieces — one per regex operator — so any regular expression becomes a machine mechanically.
Finite AutomataNFA to DFA: The Subset Construction, Step by Step
Every NFA state becomes a DFA state that is a set of NFA states — the subset construction, worked through on a machine where the blow-up actually shows up.
Finite AutomataMinimizing a DFA
Two states that can never be told apart by any input are redundant. Minimization finds and merges them, producing the smallest DFA for a language.
Finite AutomataFrom Automaton to Regex: The GNFA Method
State elimination turns any DFA or NFA into an equivalent regular expression by generalizing transition labels until only Start and Accept remain.
Pushdown Automata Explained
A pushdown automaton is a finite automaton with a stack bolted on — just enough extra memory to recognize context-free languages like balanced parentheses.
Pushdown Automata & GrammarsContext-Free Grammars
A context-free grammar generates strings from production rules instead of recognizing them state by state — the same expressive power as a PDA, seen from the other direction.