optional · CSS study notes
Finite Automata & Kleene's Theorem
Definition
A finite automaton (FA) is an abstract machine with a finite number of states used to recognize strings belonging to a regular language — the mechanism that actually implements a regex in a lexer.
Key Points
- DFA (Deterministic Finite Automaton): exactly one transition per input symbol per state; no ambiguity — directly implementable in code (fast, but can have more states).
- NFA (Non-deterministic Finite Automaton): allows multiple/zero transitions on a symbol, and ε (epsilon) moves; smaller/easier to construct from a regex, but must be converted (subset construction) to a DFA for efficient recognition.
- Kleene's Theorem: proves the equivalence of three formalisms — regular expressions, finite automata (NFA/DFA), and regular grammars all describe exactly the class of regular languages. This equivalence is why a regex can always be mechanically converted into a DFA.
- Conversion pipeline used by real compilers: Regex → NFA (Thompson's construction) → DFA (subset construction) → Minimized DFA.
Example
DFA for (a|b)*abb (strings ending in "abb") is a classic construction question: 4 states, where state 4 is the only accepting state, reached only after seeing exactly a,b,b in sequence.
📌 CSS Frequency: High — DFA construction for a given regex is one of the most repeated numeric questions.
Model Answer (short)
"By Kleene's Theorem, regular expressions, finite automata, and regular grammars are equivalent in expressive power — any regular expression can be converted to an NFA (Thompson's construction), then to an equivalent DFA (subset construction). A DFA has unique transitions per symbol, making it directly usable by a lexical analyzer, while an NFA is easier to construct but not directly executable."
📜 Past-Paper Questions & MCQs (CSS 2016–2026)
Questions that depend on a figure are solved from the transitions as read from the scanned paper. If your copy differs, use the same method.
2018 · Paper-I · Q8(c) · 5 marks
Q. The DFA for language L has start state q0 (loop on a), q0 on b → q1 (accepting), and q1 on a or b → q2 (dead state). Find the DFA for L².
Ans.
- The given DFA accepts L = a*b (any number of a's, then exactly one b).
- L² = ab ab (two strings of L joined).
- DFA for L²:
| State | a | b | Meaning |
|---|---|---|---|
| p0 (start) | p0 | p1 | reading the a's of the first part |
| p1 | p1 | p2 | first b seen, reading the second part's a's |
| p2 (accepting) | dead | dead | second b seen, nothing may follow |
| dead | dead | dead | reject |
2018 · Paper-I · Q8(d) · 5 marks
Q. Convert the given DFA (five states, edges labelled 3 and 6) to a regular expression.
Ans. (The edge labels in the scan are too small to read reliably, so only the method is given.)
- State elimination: add a new start state and a new single final state joined by ε-edges. Remove the intermediate states one at a time. When removing a state s, for every pair (p, q) with edges p→s and s→q, add the edge p→q labelled R(p,s) · R(s,s)* · R(s,q), and combine parallel edges with
|. - Arden's theorem: write an equation for each state (X = aX + b has the solution X = a*b) and solve for the start state.
- The regular expression is the label on the last remaining edge from the start to the final state.
2020 · Paper-I · Q7(b) · 5 marks
Q. Create the state transition table from the given graph.
Ans. (Transitions as read: q0 –a,b→ q1; q1 –a→ q2; q1 –b→ q3; q3 –a→ q2; q3 –b→ q4; q2 –a,b→ q4; q4 –a,b→ q5; q5 loops on a,b.)
| State | a | b |
|---|---|---|
| → q0 | q1 | q1 |
| q1 | q2 | q3 |
| q2 | q4 | q4 |
| q3 | q2 | q4 |
| q4 | q5 | q5 |
| q5 | q5 | q5 |
2020 · Paper-I · Q7(c) · 4 marks
Q. Draw a finite automaton that accepts the inputs JIM, JMI, JJIIM and JJMMII.
Ans. The automaton is a tree of states, one path per word. Any other input goes to a dead state.
- JIM: s0 –J→ s1 –I→ s2 –M→ f1
- JMI: s1 –M→ s3 –I→ f2
- JJIIM: s1 –J→ s4 –I→ s5 –I→ s6 –M→ f3
- JJMMII: s4 –M→ s7 –M→ s8 –I→ s9 –I→ f4
- Accepting states: f1, f2, f3, f4.
2021 · Paper-I · Q6(a) · 8 marks
Q. Convert the NFA to a DFA. (NFA as read: q0 –0→ q0, q0 –1→ {q1, q2}; q1 –0→ {q1, q2}, q1 –1→ q2; q2 –0→ {q0, q1}, q2 –1→ q1; start q0, accepting q2.)
Ans. Subset construction:
| DFA state | On 0 | On 1 |
|---|---|---|
| A = {q0} (start) | {q0} = A | {q1, q2} = B |
| B = {q1, q2} (accepting) | {q1, q2} ∪ {q0, q1} = {q0, q1, q2} = C | {q2} ∪ {q1} = {q1, q2} = B |
| C = {q0, q1, q2} (accepting) | {q0, q1, q2} = C | {q1, q2} = B |
- A DFA state is accepting if it contains the NFA's accepting state q2 (here B and C). Three DFA states are enough.
2022 · Paper-I · Q8(a) · 8 marks
Q. Draw a finite automaton over Σ = {0, 1} that accepts all binary strings starting and ending with 0 (a single "0" counts).
Ans.
| State | 0 | 1 | Meaning |
|---|---|---|---|
| q0 (start) | q1 | dead | nothing read yet; the first symbol must be 0 |
| q1 (accepting) | q1 | q2 | started with 0 and the last symbol read is 0 |
| q2 | q1 | q2 | started with 0 but the last symbol is 1 |
| dead | dead | dead | started with 1, reject |
- Regular expression:
0 | 0(0|1)*0.
2023 · Paper-I · Q7(a) · 8 marks
Q. Design and draw a finite automaton that recognises all strings containing "001" as a substring.
Ans.
| State | 0 | 1 | Meaning |
|---|---|---|---|
| s0 (start) | s1 | s0 | no useful progress |
| s1 | s2 | s0 | last symbol was 0 |
| s2 | s2 | s3 | last two symbols were 00 |
| s3 (accepting) | s3 | s3 | 001 has been found, stay accepted |
2023 · Paper-I · Q7(b) · 6 marks
Q. From the state diagram extract Q, Σ, q₀, F and δ. (Diagram as read: a –0→ a, a –1→ b; b –1→ a, b –0→ c; c –0→ b, c –1→ c; start a, accepting c.)
Ans.
- Q = {a, b, c} · Σ = {0, 1} · q₀ = a · F = {c}
- δ: δ(a,0) = a, δ(a,1) = b, δ(b,0) = c, δ(b,1) = a, δ(c,0) = b, δ(c,1) = c.
2026 · Paper-I · Q7(a) · 6 marks
Q. Construct a DFA for the regular expression (a|b)*abb.
Ans. The standard four-state DFA, where each state remembers how much of "abb" has just been matched:
| State | a | b |
|---|---|---|
| 0 (start) | 1 | 0 |
| 1 (seen a) | 1 | 2 |
| 2 (seen ab) | 1 | 3 |
| 3 (seen abb, accepting) | 1 | 0 |
2020 · Paper-I · Q7(d) · 6 marks
Q. Determine which of these inputs are valid for the FSM shown: (i) aaaaa (ii) ababa (iii) abcabc (iv) abccba (v) acbcd (vi) acbcdcd.
Ans.
- Rule for every string: start in the start state S1. For each symbol follow the transition with that label. The string is valid (accepted) only if every symbol has a transition and the last state reached is a final (accepting) state. If a symbol has no transition from the current state, the string is rejected at once.
- Transitions I can read from the scan: S1 –a→ S2, S1 –b→ S2, S2 –a→ S2 (loop), S2 –c→ S4, S3 –a→ S1, S3 –b→ S4, S3 –c→ S4. The scan does not show the final state reliably, so I take S4 as final.
- Trace with this reading:
| Input | Path | Result |
|---|---|---|
| aaaaa | S1 → S2 → S2 → S2 → S2 → S2 | Ends in S2, which is not final: rejected |
| ababa | S1 –a→ S2, then b has no transition from S2 | Rejected |
| abcabc | S1 –a→ S2, then b has no transition from S2 | Rejected |
| abccba | S1 –a→ S2, then b has no transition from S2 | Rejected |
| acbcd | S1 –a→ S2 –c→ S4, then b has no transition from S4 | Rejected |
| acbcdcd | Same path as above, and the symbol d is not in the alphabet | Rejected |
- Caution: a question of this kind normally has some accepted strings, so I have probably misread an arrow or the final state in the scan. Use the method above on your printed diagram, or send me a clearer picture of the figure (or type the transitions and the final state) and I will complete the table.