DFA Fundamentals and Construction

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.

Cover the answer, recall, then check. 12 cards on DFA fundamentals.

Q1. Extend δ to strings: what is δ̂(q, w)?
A1. δ̂(q, ε) = q and δ̂(q, wa) = δ(δ̂(q, w), a) — the state reached after reading the whole string w from q.

Q2. Formally, when does a DFA accept a string w?
A2. When δ̂(q0, w) ∈ F.

Q3. What language does a DFA define?
A3. L(M) = { w ∈ Σ* : δ̂(q0, w) ∈ F } — a regular language.

Q4. Why is a DFA called "deterministic" and "complete"?
A4. Deterministic: exactly one move per (state, symbol). Complete/total: δ is defined for every such pair (no missing edges).

Q5. Can a DFA have ε-transitions or multiple start states?
A5. No — no ε-moves, and exactly one start state. Those are NFA features.

Q6. How does a DFA differ from an NFA in accepting a string?
A6. A DFA follows one unique path; an NFA accepts if any of its (possibly many) paths reaches a final state.

Q7. What must every "complete" DFA drawing include for a non-accepting sink?
A7. A dead/trap state so δ stays total; all its transitions self-loop and it is never accepting.

Q8. For a DFA over Σ with |Q| = n states, what is the maximum number of transitions in the diagram?
A8. n·|Σ| (one edge per state per symbol).

Q9. If two states are reached by the same set of future accepted suffixes, what can be said?
A9. They are equivalent (indistinguishable) and can be merged during minimization.

Q10. Is the minimal DFA for a regular language unique?
A10. Yes — up to renaming of states (a consequence of the Myhill–Nerode theorem).

Q11. What does it mean for a state to be unreachable, and why remove it?
A11. No string leads to it from q0; it can't affect L(M), so it's dropped before/after minimization.

Q12. Give the DFA for L = Σ* (all strings) and for L = ∅.
A12. Σ*: single accepting state self-looping on all symbols. ∅: single non-accepting state self-looping on all symbols.