CSS Computer Science (Optional) — Paper-I, Section-B, Topic VI. This page covers Section-B Compiler Construction questions extracted from the CSS Computer Science Paper-I past papers, 2016 through 2026 (54 question-patterns total: 44 subjective sub-parts and 10 MCQs). Content is grouped by year, most recent first.

Q1. Constructing a DFA for a Regular Expression

Appeared: 2026, Q7(a)

Construct a Deterministic Finite Automaton (DFA) for the regular expression (a|b)*abb.

Solution:

The language (a|b)*abb matches: any string of a's and b's, ending in exactly abb.

States: track how much of the suffix abb has been matched so far.

• q0 (start): no relevant suffix matched yet
• q1: last character seen was a (progress toward abb)
• q2: last two characters seen were ab
• q3 (accepting): last three characters seen were abb — string accepted

Transition table:

Reasoning for each transition:

• q0 on a → q1 (one step into a possible abb suffix); q0 on b → q0 (a lone b matches nothing of abb, stay at start)
• q1 on a → q1 (a new a restarts the "a" progress — still just "last char was a"); q1 on b → q2 (now have ab)
• q2 on a → q1 (breaks the ab, but this new a itself starts fresh progress); q2 on b → q3 — accept, abb just completed
• q3 on a → q1 (a further a restarts progress — the string could still end in another abb later); q3 on b → q0 (breaks the pattern entirely — abbb no longer ends in abb from this point)

Key reasoning points: this is the single most frequently reused DFA construction in compiler-theory exams (it appears, sometimes with aab/bab instead of abb, across many university and competitive-exam papers) precisely because it forces the student to handle overlapping suffixes correctly (e.g., realizing that from q2, an a doesn't send you back to q0 — it sends you to q1, since that a itself is progress toward a new abb). Getting the overlap transitions right is what separates a correct DFA from a plausible-looking wrong one.