Language
A set of finite strings over a finite alphabet Σ. Σ* includes the empty string ε.
Find a concept
REFERENCE SHEET
Finite automata & regular languages
Finite memory recognizes patterns whose relevant history has only finitely many cases.
Before this Sets & maps, Boolean logic, circuits & satisfiability
L(A) = {w ∈ Σ* : δ*(q₀,w) ∈ F}
Definitions
DFA
A deterministic finite automaton (Q,Σ,δ,q₀,F) has finitely many states, a total transition function δ:Q×Σ→Q, a start state, and accepting states. δ* extends δ to whole strings.
Regular language
A language recognized by some DFA. NFAs may have several possible transitions and ε-transitions; acceptance means at least one run accepts.
Key theorems
Equivalent descriptions
DFAs, NFAs, and formal regular expressions describe exactly the regular languages. Subset construction converts an n-state NFA to a DFA with at most 2ⁿ states.
Closure
Regular languages are closed under union, intersection, complement relative to Σ*, concatenation, and Kleene star.
Myhill–Nerode
Define x∼L y when for every suffix z, xz∈L iff yz∈L. L is regular exactly when this relation has finitely many classes; their number equals the minimum DFA state count.
Notable applications
Lexing
Recognize tokens such as identifiers and numeric literals.
Finite-state protocols
Model systems whose relevant state is finite, then analyze reachable or accepting states.
Work it out
Try before revealing01 / Construct
Describe a DFA over {0,1} accepting strings with an even number of 1s.
Hint
Track parity rather than the entire prefix.
Solution
Use states E and O, start E, accepting set {E}. On 0 stay in the same state; on 1 switch. ε is accepted because it has zero 1s.
02 / Prove
Show L={0ⁿ1ⁿ:n≥0} is not regular using distinguishable prefixes.
Hint
Compare prefixes 0ⁱ and 0ʲ with i≠j; append 1ⁱ.
Solution
0ⁱ1ⁱ is in L, but 0ʲ1ⁱ is not. Thus all prefixes 0ⁱ occupy different equivalence classes. There are infinitely many, so Myhill–Nerode rules out regularity.
03 / Prove
Use the pumping lemma to show {0ⁿ1ⁿ:n≥0} is not regular.
Hint
For pumping length p, choose 0ᵖ1ᵖ. Every allowed pumped segment lies in the initial zeros.
Solution
Suppose the language is regular with pumping length p. For every decomposition 0ᵖ1ᵖ=xyz with |xy|≤p and |y|>0, y consists of k≥1 zeros. Pumping down gives xz=0ᵖ⁻ᵏ1ᵖ, outside the language. Thus no permitted decomposition satisfies the pumping conclusion, a contradiction.
Connect the ideas
Build on this
These sheets use this topic as a prerequisite.
Go deeper
Further reading and full-length treatments: