Finite Automata

A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F):

• Q: finite set of states
• Σ: input alphabet
• δ: Q × Σ → Q (transition function — exactly one next state per (state, symbol))
• q₀ ∈ Q: start state
• F ⊆ Q: accept (final) states

A DFA accepts an input string if, starting from q₀ and applying δ for each symbol, it ends in some state in F.

NFA (Non-deterministic): δ: Q × (Σ ∪ {ε}) → 2^Q. Multiple next states (or none). ε-transitions allowed.

Key theorem: every NFA has an equivalent DFA. The conversion (subset construction) can blow up the state count exponentially (up to 2^|Q|), but the recognized language is the same.

Regular languages. A language is regular iff it's recognized by some DFA (equivalently NFA, ε-NFA, regular expression).

Closure properties — regular languages are closed under:

• Union, intersection, complement, difference
• Concatenation
• Kleene star
• Reverse
• Homomorphism

Decidable problems for DFA:

• Membership (is string w in L?) — O(|w|).
• Emptiness (is L = ∅?) — graph reachability.
• Equivalence of two DFAs — comparing their minimal forms.
• Minimization — Hopcroft's algorithm O(n log n).

Pumping Lemma for regular languages. If L is regular, there exists a pumping length p such that every string s ∈ L with |s| ≥ p can be split as s = xyz, satisfying:

1. |xy| ≤ p
2. |y| ≥ 1
3. xy^i z ∈ L for all i ≥ 0.

Used to prove a language is NOT regular (by contradiction).

Classic non-regular language: L = { aⁿbⁿ | n ≥ 0 }.

Proof: assume regular with pumping length p. Take s = a^p b^p. By condition 1, |xy| ≤ p, so xy consists only of a's. y must be one or more a's. Pump once → xy²z has more a's than b's → not in L. Contradiction. So L is not regular.

Other classics not regular:

• { ww | w ∈ Σ* }
• { a^p | p is prime }
• Balanced parentheses (with arbitrary nesting depth) — requires a stack, hence Context-Free, not regular.

Regex → NFA → DFA pipeline:

Regex (POSIX or extended) → Thompson construction → ε-NFA → Subset construction → DFA → Minimization → Optimal DFA.

This is the heart of grep, lex/flex, and most pattern-matching engines (though many use NFAs directly to support backreferences, which take you beyond regular).

GATE-style sample question. How many states in the minimal DFA for L = { strings over {0, 1} divisible by 3 when read as binary }?

Answer: 3 — states represent remainders 0, 1, 2 modulo 3. Start = accept = remainder 0. Transition function: on 0 → 2r mod 3; on 1 → (2r+1) mod 3.

A Deterministic Finite Automaton is a 5-tuple M = (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is the input alphabet, δ: Q × Σ → Q is the transition function (TOTAL and single-valued), q0 is the start state, and F ⊆ Q is the set of accepting states. KEY PROPERTY: for each (state, symbol) pair there is EXACTLY ONE transition — no choices, no epsilon moves. A string w is accepted if δ*(q0, w) ∈ F. The language L(M) is the set of all accepted strings. Memory aid: 'DFA = Definite, Fixed, Always one move.' Because transitions are total, a complete DFA on |Σ| symbols and n states has exactly n×|Σ| transition entries.

Two recurring GATE patterns: (1) Binary numbers divisible by k → use k states labeled by remainder mod k. Reading bit b updates state r to (2r + b) mod k. Start = accept = state 0. This needs exactly k states. (2) Strings containing a fixed substring of length m → needs (m+1) states minimum (track longest matched prefix, like KMP). 'Ending with' pattern of length m also needs states tracking the suffix. Shortcut: 'divisible-by-k' = k states; 'last/first symbol' constraints multiply state counts. For 'i-th symbol from end equals x' you need 2^i states (must remember last i symbols).

States {q0, q1, q2} represent remainder mod 3. δ(qr, b) = q(2r+b) mod 3. Transitions: δ(q0,0)=q0, δ(q0,1)=q1; δ(q1,0)=q2, δ(q1,1)=q0; δ(q2,0)=q1, δ(q2,1)=q2. Start state q0, accepting state {q0}. Check '110' (=6): q0 →1→ q1 →1→ q0 →0→ q0, accepted (6 mod 3 = 0). Check '101' (=5): q0→1→q1→0→q2→1→q2, rejected (5 mod 3 = 2). This 3-state machine is minimal — divisibility-by-k DFAs cannot have fewer than k states.

Every NFA has an equivalent DFA recognizing the same language (Rabin-Scott). Conversion uses SUBSET CONSTRUCTION: each DFA state is a SET of NFA states. DFA start state = epsilon-closure of the NFA start state. For each DFA state S and input symbol a: new state = epsilon-closure(union of move(q,a) for all q in S). A DFA state is ACCEPTING if it contains at least one NFA accepting state. The empty set {} is the DEAD/TRAP state (handles missing transitions). Bound: an n-state NFA yields a DFA with AT MOST 2^n reachable states (worst-case exponential blowup is achievable). Only create REACHABLE subsets to keep it small. Epsilon-closure of q = all states reachable from q using epsilon-transitions only (including q itself).

GATE-critical points: (1) NFA and DFA are EQUIVALENT in power — both accept exactly the regular languages; epsilon-transitions add no extra power. (2) The DFA may need up to 2^n states; the language a^(n-1)(a|b)^* style constructions force exponential blowup. (3) The resulting DFA is COMPLETE (every state has a transition on every symbol — missing ones go to the dead state). (4) Number of states is an UPPER bound, not always reached; minimize afterward via DFA minimization if asked. (5) Don't forget epsilon-closures at EVERY step — a frequent error is closing only the start state. (6) A subset containing any NFA final state is final, even if it also contains non-final states. Memory aid: 'states = subsets, start = closure, final = contains a final.'

NFA: states {q0,q1}, start q0, final {q1}, no epsilon. Transitions: q0 on a -> {q0,q1}; q0 on b -> {q0}; q1 on a -> {}; q1 on b -> {}. DFA start = {q0}. From {q0}: on a -> {q0,q1}; on b -> {q0}. New state {q0,q1} (contains q1 => ACCEPTING): on a -> move(q0,a) U move(q1,a) = {q0,q1} U {} = {q0,q1}; on b -> {q0} U {} = {q0}. DFA states: {q0}(start), {q0,q1}(final). Transition table: {q0} --a--> {q0,q1}, {q0} --b--> {q0}; {q0,q1} --a--> {q0,q1}, {q0,q1} --b--> {q0}. This DFA accepts strings ending in 'a' (the language (a|b)*a). Only 2 of the possible 2^2=4 subsets are reachable, illustrating that the 2^n bound is rarely tight.

An NFA is M = (Q, Σ, δ, q0, F) where δ: Q × Σ → 2^Q maps to a SET of states (possibly empty). An ε-NFA additionally allows δ: Q × (Σ ∪ {ε}) → 2^Q. Acceptance is by EXISTENCE: w is accepted if at least one computation path ends in a final state. Key fact: NFAs, ε-NFAs, and DFAs are EQUIVALENT in power — all recognize exactly the regular languages. NFAs never accept more languages; they only offer more compact descriptions. Memory aid: 'NFA = guess and check — accept if any guess works.' The ε-closure of a state set is all states reachable using only ε-moves.

To convert an NFA with n states to a DFA: each DFA state is a SUBSET of NFA states. Start = ε-closure({q0}). For DFA state S and symbol a: δ_DFA(S,a) = ε-closure(∪{δ(q,a) : q ∈ S}). A DFA state is accepting if it contains any NFA final state. UPPER BOUND on DFA states = 2^n (the number of subsets). In the WORST case this bound is tight (e.g., 'n-th symbol from the end' languages). Usually far fewer subsets are reachable. Shortcut: only enumerate REACHABLE subsets, not all 2^n. The empty set ∅ acts as the dead state.

Language L_k = strings over {0,1} whose k-th symbol from the END is 1. An NFA recognizes L_k with k+1 states (guess the position, then count k-1 more). But the MINIMAL DFA needs exactly 2^k states because it must remember the last k symbols seen. This is the classic example proving the subset-construction 2^n upper bound is tight. For k=2: NFA has 3 states, minimal DFA has 4 states. Memory aid: 'NFA guesses where; DFA must remember everything.' GATE frequently asks for DFA state counts of such 'from-the-end' languages.

Two strings x, y are equivalent w.r.t. language L (written x ≡_L y) if for EVERY string z: xz ∈ L ⟺ yz ∈ L. The number of equivalence classes of ≡_L is the index of L. Myhill-Nerode Theorem: L is regular ⟺ ≡_L has FINITE index, and that index equals the number of states in the MINIMAL DFA for L. Use it two ways: (1) prove non-regularity by exhibiting infinitely many pairwise-distinguishable strings; (2) compute the minimal DFA size by counting distinguishable classes. Memory aid: 'Distinguishable suffixes = distinct states.' Two strings need different states iff some suffix tells them apart.

To minimize a DFA: (1) Remove unreachable states. (2) Initially mark every pair (p,q) where exactly one is final — these are distinguishable. (3) Repeat: mark pair (p,q) if for some symbol a, the pair (δ(p,a), δ(q,a)) is already marked. (4) Continue until no change. (5) Unmarked pairs are EQUIVALENT and get merged into one state. Equivalently, partition refinement (Moore/Hopcroft) splits classes until stable. Hopcroft's algorithm runs in O(n log n · |Σ|). The result is the UNIQUE (up to isomorphism) minimal DFA. Pitfall: always delete unreachable states FIRST, otherwise the count is wrong.

Consider strings a^0, a^1, a^2, … For any i ≠ j, take suffix z = b^i. Then a^i b^i ∈ L but a^j b^i ∉ L, so a^i and a^j are distinguishable. Thus there are infinitely many ≡_L classes ⟹ by Myhill-Nerode L = {a^n b^n} is NOT regular — no finite DFA exists. The same suffix-distinguishing trick proves {ww}, {a^n b^n c^n}, and {palindromes} non-regular. Memory aid: pick an infinite family of prefixes, find one suffix per pair that separates them. Contrast with the pumping lemma, which only gives a necessary (not sufficient) condition.

If L is regular, there exists a pumping length p such that every w ∈ L with |w| ≥ p can be split as w = xyz where: (1) |y| ≥ 1 (y non-empty), (2) |xy| ≤ p, and (3) for all i ≥ 0, xy^i z ∈ L. To PROVE a language non-regular: assume regular, the adversary picks p; YOU choose a clever w (|w| ≥ p); for every valid split the adversary makes, find one i (often i=0 or i=2) so xy^i z ∉ L. It is a NECESSARY but NOT sufficient condition — some non-regular languages satisfy it. Memory aid: 'Long strings in a regular language must contain a loop you can pump.'

Regular languages are CLOSED under: union, intersection, complement, concatenation, Kleene star, reversal, difference, homomorphism, inverse homomorphism, prefix/suffix/substring, and quotient. They are NOT closed under: infinite union or infinite intersection. Useful proof trick: if L1 is regular and L1 ∩ L2 is non-regular, then L2 must be non-regular (since regular ∩ regular = regular). Memory aid: 'Regular is a fortress — closed under all the standard boolean and rational operations.' Complement closure follows from swapping final states in a complete DFA; intersection from the product (cross) construction.

Let L = {0^n 1^n : n ≥ 0}. Assume regular with pumping length p. Choose w = 0^p 1^p (|w| = 2p ≥ p). By condition |xy| ≤ p, both x and y lie entirely within the 0's, so y = 0^k with k ≥ 1. Pump i = 2: xy^2 z = 0^(p+k) 1^p, which has more 0's than 1's, so it is NOT in L. Contradiction ⟹ L is not regular. Tip: choosing i = 0 (deleting y) also works: 0^(p−k)1^p ∉ L. Always pick w so that the constrained region |xy| ≤ p forces y into a 'fragile' part.