Languages and deterministic finite automata
Goals and conventions
Model a language by the information a machine must remember. Prerequisites are sets and functions. An alphabet Σ is a finite set of symbols. A string is a finite sequence of symbols; ε is the length-zero string. Σ* contains every finite string, including ε. A language is any subset of Σ*. The empty language ∅ and the singleton language {ε} are different: their cardinalities are zero and one. Here every automaton reads its entire input before deciding acceptance.
For languages A and B, AB={xy:x∈A,y∈B}. Concatenation is generally not commutative. A^0={ε} and A* is the union of A^n for n≥0. Thus ∅={ε}, whereas ∅A=∅. The complement of A must name a universe: throughout it is Σ\A for the specified alphabet.
1. The DFA contract
A DFA is (Q,Σ,δ,q0,F), with finite nonempty Q, total function δ:Q×Σ→Q, start q0∈Q and final states F⊆Q. A missing edge in a drawing is shorthand for a rejecting sink only when that convention is stated. Define δ(q,ε)=q and δ(q,wa)=δ(δ(q,w),a). The language is {w:δ(q0,w)∈F}. Visiting a final state in the middle of a string is insufficient. The empty string is accepted exactly when q0∈F.
Think of each state as an invariant about the prefix already read. A state does not need to store the entire prefix; it stores enough information to determine what any future suffix will do.
2. Worked construction: even number of 1s
Over {0,1}, let E mean an even number of 1s so far, and O mean odd. Start and accept in E. On 0, each state stays where it is. On 1, E goes to O and O goes to E. Trace 1011: E→O→O→E→O, so reject. Trace 101: E→O→O→E, so accept.
Proof of correctness by induction on prefix length: ε has zero 1s, so the invariant initially holds. Reading 0 preserves parity; reading 1 reverses it. The transitions do exactly these updates. Therefore the invariant holds for every prefix, and the accepting state corresponds precisely to the desired property. This proof establishes both that every desired word is accepted and that no undesired word is accepted.
3. Worked construction: strings ending in 01
Use states A, B, C for the longest suffix of the current prefix that is also a prefix of the target 01: ε, 0, 01 respectively. Start A; only C accepts. Transitions are A:0→B,1→A; B:0→B,1→C; C:0→B,1→A. Trace 001: A→B→B→C. Trace 010: A→B→C→B, so reject. Reaching C after two symbols does not cause early acceptance of 010.
The three states are necessary: suffix 1 distinguishes B from A and C, while ε distinguishes C from A. More generally, two prefixes requiring different answers for some common suffix cannot end in the same DFA state.
4. Counting modulo a fixed integer
For the unary language {a^n:n mod 3=1}, use q0,q1,q2 representing the length residue modulo 3. On a, cycle q0→q1→q2→q0; accept q1. This uses finite memory even though the language is infinite. In contrast, remembering an unbounded exact count for later equality may exceed finite-state power. Do not infer nonregularity merely because infinitely many strings occur: a* is infinite and regular.
Pitfalls and exam method
- State the alphabet, start state, accepting states and every transition.
- Test ε, the shortest accepted string, and a near miss.
- Prove an invariant instead of trusting a few sample traces.
- States count memory categories; symbols count alphabet size. Neither is the number of accepted strings.
- Complement a DFA by exchanging final/nonfinal states only after making its transition function total.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Which language contains exactly one string?
A. ∅ B. {ε} C. {0,1}* D. ∅{a}
Answer: B
A: ∅ contains no strings.
B: Its only element is the empty string.
C: It contains infinitely many strings.
D: Concatenation with ∅ remains empty.
P02. In the even-1s DFA, where does 11010 finish?
A. E, accepted B. O, accepted C. E, rejected D. O, rejected
Answer: D
A: There are three 1s, not an even count.
B: O is not final.
C: E would be final, but is not reached.
D: Three 1s yield O, which rejects.
P03. For the suffix-01 DFA, which word is accepted?
A. 010 B. 001 C. ε D. 11
Answer: B
A: Its final suffix is 10.
B: It ends in 01 and reaches C.
C: The start A is not final.
D: It ends in 11 and reaches A.
P04. What is ∅*?
A. ∅ B. {ε} C. Σ* for every Σ D. {∅}
Answer: B
A: The zero-fold concatenation contributes ε.
B: The only contribution is A^0={ε}.
C: No nonempty word can be formed.
D: ∅ is a language, not the empty word.
P05. A complete DFA accepts ε exactly when:
A. Every state is final B. The alphabet is empty C. The start state is final D. There is a self-loop
Answer: C
A: This is sufficient but unnecessary.
B: Alphabet emptiness does not determine finality.
C: No input is read, so the machine stays at its start.
D: A loop need not be on a final state.
P06. A residue-3 DFA starts at q0 and accepts q1. Which length is accepted?
A. 6 B. 8 C. 9 D. 10
Answer: D
A: 6 mod 3 is 0.
B: 8 mod 3 is 2.
C: 9 mod 3 is 0.
D: 10 mod 3 is 1.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in