• Overview
• Details
• Exercises

Regular languages are recognized by deterministic and nondeterministic finite automata (DFAs, NFAs) and described by regular expressions. These models are equivalent in expressive power and underpin lexers and pattern matching.

• DFA: tuple (Q, Σ, δ, q₀, F); total transition function; language L(M).
• NFA: ε-transitions, subset construction to DFA; equivalence to DFA.
• Regex: union, concatenation, Kleene star; equivalence to NFA via Thompson construction; to DFA via subset.
• Closure properties: union, concatenation, star, intersection, complement; decision problems (emptiness, finiteness, membership).
• Minimization: Myhill–Nerode theorem; partition refinement algorithm; canonical minimal DFA.
• Limitations: non-regular languages (e.g., a^n b^n); pumping lemma for regular languages.

1. Convert an NFA with ε-transitions to an equivalent DFA via subset construction; draw both automata.
2. Use Myhill–Nerode to prove minimality of a DFA for strings over {0,1} divisible by 3 in binary.
3. Given a regex, build an NFA (Thompson) then determinize and minimize; compare state counts.