🔥 Most Repeated — Compiler Construction

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.

---

Q2. Lexeme vs Token vs Pattern

Appeared: 2026, Q7(b)

Explain the difference among lexeme, token, and pattern with examples.

Solution:

One-line summary: the pattern is the rule, a lexeme is one specific piece of source text that satisfies that rule, and a token is the name/category the lexical analyzer assigns to that lexeme so the parser can work with categories instead of raw text.

Key reasoning point: many different lexemes (total, count, sum, x1) can all map to the same token (IDENTIFIER) because they all match the same pattern — this many-to-one relationship (lexeme → token, via a pattern) is exactly what the question is testing.

---

Q3. Register Allocation for Three-Address Code with Limited Registers

Appeared: 2026, Q7(c)

Consider the three-address code: t1 = a + b, t2 = t1 + c, t3 = t2 + d. If the machine has only two registers, how should the compiler allocate registers to minimize memory spills?

Solution:

With only 2 registers (R1, R2) and three temporaries that form a dependency chain (t2 needs t1; t3 needs t2), the key insight is that once a temporary has been consumed by the next instruction, its register can be reused — there is no need to keep all three temporaries live simultaneously.

Allocation strategy (register reuse along the dependency chain):

Zero spills needed — because each temporary is used exactly once, immediately by the next instruction, the compiler can always free a register the moment its value has been consumed, keeping the live-variable count at ≤ 2 throughout.

Key reasoning points: this is a classic register allocation / liveness analysis question — the compiler determines each variable's live range (from definition to last use) and reuses a register the instant a value's live range ends. If the code instead needed a, b, c, and d all simultaneously (e.g., a more branching computation), more than 2 registers would be required and the compiler would have to spill one value to memory (store it temporarily and reload it later) — mentioning when a spill becomes unavoidable, not just describing this spill-free case, shows deeper understanding.

---

Q4. Lexical Analyzer Processing a Malformed Input String

Appeared: 2026, Q8(a)

Suppose a lexical analyzer is scanning code and encounters the following input string: 9var = x + 12abc; Describe step-by-step how the lexical analyzer processes this input, identifies errors, and generates tokens. Explain which specific rules of lexical analysis it uses.

Solution:

Step-by-step scan (using maximal munch / longest-match, the standard lexical-analysis rule):

1. 9var — the analyzer starts reading 9, a digit, so by its pattern rules it expects a NUMBER token (digit+). It continues consuming characters using maximal munch (always extend the match as far as possible) and hits v, which is a letter, not a digit. A NUMBER pattern cannot contain letters, so this produces a lexical error: 9var is an invalid identifier (identifiers must start with a letter or underscore, per the pattern letter (letter | digit)* — never a digit). The analyzer reports the error and typically recovers by skipping the offending characters and resuming the scan.
2. = — matches the ASSIGN_OP token exactly (single-character pattern).
3. x — matches letter (letter|digit)*, forming a valid IDENTIFIER lexeme.
4. + — matches the PLUS_OP token.
5. 12abc — same error class as step 1: scanning starts with digits 12 (valid start of a NUMBER), but then hits letters abc. Since a NUMBER pattern can't include letters and an IDENTIFIER pattern can't start with digits, 12abc matches neither token pattern cleanly — another lexical error (invalid identifier/malformed token).
6. ; — matches the SEMICOLON token, marking the statement's end.

Resulting token stream (valid tokens only): ASSIGN_OP, IDENTIFIER(x), PLUS_OP, SEMICOLON — with two lexical errors flagged for 9var and 12abc.

Specific lexical-analysis rules/concepts used:

• Maximal munch (longest match): the scanner always consumes the longest possible sequence of characters that matches some pattern before deciding on a token.
• Pattern matching via regular expressions: each token type (IDENTIFIER, NUMBER, operators, punctuation) has a defining regex; a lexeme is accepted only if it fully matches one.
• Error detection and recovery: when no pattern matches (or an identifier-like token starts with a digit), the lexer reports a lexical error and applies a recovery strategy (commonly: skip the invalid characters and continue scanning) so that one bad token doesn't halt the entire compilation pass.

Exam angle: the core insight examiners are checking for is that identifiers must start with a letter (or underscore), never a digit — both 9var and 12abc are invalid for exactly this reason, and explicitly naming "maximal munch" as the scanning strategy is what separates a mechanical answer from one showing real understanding of lexical analysis.

---

2025

Q5. Regex + DFA for Strings Starting with "baa"

Appeared: 2025, Q8(a), 6 marks

Create a regular expression for the language that always starts with string " baa ". Also draw the deterministic finite automata (DFA) for such language. Provide a clear explanation of each step.

Solution:

Regular expression: baa(a|b)* over alphabet {a,b} — i.e., the string "baa" followed by any number (including zero) of further a's or b's.

DFA description (states and transition table), since Σ = {a,b}:

• q0 (start state): on 'b' → q1; on 'a' → qd (dead/trap state, since the string must begin with 'b').
• q1 (after seeing 'b'): on 'a' → q2; on 'b' → qd (the required next symbol is 'a').
• q2 (after seeing 'ba'): on 'a' → q3 (accepting); on 'b' → qd.
• q3 (accepting state, after seeing 'baa'): on 'a' → q3 (self-loop); on 'b' → q3 (self-loop) — once "baa" has been matched, any further a's or b's keep the string accepted.
• qd (dead/trap state, non-accepting): on 'a' → qd; on 'b' → qd — absorbs any string that failed to start with "baa".

Transition table:

Explanation: the DFA walks the prefix "b","a","a" through q0→q1→q2→q3 exactly tracking the required prefix; any deviation from this exact sequence is routed to the dead state qd, from which it can never escape, correctly rejecting all strings not starting with "baa". Once state q3 is reached the automaton accepts and stays accepting for any suffix, matching (a|b)*.

---

Q6. Instruction Scheduling in Code Generation

Appeared: 2025, Q8(b), 6 marks

What is Instruction Scheduling? Explain its role during code generation process.

Solution:

Instruction scheduling is a compiler optimization, performed during (or just after) code generation, that reorders the machine instructions produced for a basic block or a larger region without changing the program's semantics/output, in order to better exploit the target processor's pipeline and functional units.

Role during code generation:

• Hides pipeline stalls: modern pipelined CPUs need several cycles before the result of one instruction is available; if a dependent instruction immediately follows, the pipeline stalls. The scheduler moves independent instructions in between to fill these gaps.
• Avoids hazards: it reorders instructions so that data hazards (RAW/WAR/WAW) and structural hazards on functional units are minimized, without inserting extra NOPs where avoidable.
• Maximizes instruction-level parallelism: on superscalar/VLIW architectures, the scheduler groups independent instructions so multiple functional units can execute them concurrently.
• Respects dependencies: it builds a data-dependency graph of the basic block and only reorders instructions that have no dependency conflict, guaranteeing correctness is preserved.

It is typically applied after (or interleaved with) register allocation as one of the final back-end optimization passes, directly before final machine code emission, and it significantly improves the runtime performance of the generated code on pipelined hardware.

---

Q7. Parse Trees and Language Membership

Appeared: 2025, Q8(c), 8 marks

What is a parse tree? How the parse tree is used to check whether a specific string belongs to a language or not. Provide example to elaborate this.

Solution:

A parse tree (derivation tree) is a hierarchical, ordered tree representation of how a string is derived from the start symbol of a context-free grammar. Its root is the grammar's start symbol, each internal node is a non-terminal expanded according to one of its production rules, and the leaves, read left to right, spell out the input string (the yield of the tree).

Using it to check language membership: to test whether a string w belongs to a language L(G) defined by grammar G, a parser attempts to construct a parse tree for w by applying G's production rules (top-down, e.g., LL parsing, or bottom-up, e.g., LR parsing). If such a tree can be built whose leaves exactly match w and whose root is the start symbol, then w is successfully derived and therefore belongs to L(G); if no valid sequence of rule applications can produce w (parsing fails/gets stuck), then w does not belong to the language (a syntax error is reported).

Example: grammar for simple expressions:
E → E + T | T
T → T * F | F
F → id

For the string "id + id * id":

• Root: E
• E → E + T
• Left E → T → F → id (first id)
• T → T * F → F * F → id * id (second and third id's)

The resulting tree has root E, branches for '+' and '*' respecting precedence (multiplication nested deeper, binding tighter), and its leaves read left to right give exactly "id + id * id". Since a complete, valid parse tree was constructed, the string is confirmed to belong to the language generated by this grammar; if instead the input were "id + + id", no legal sequence of productions could generate it, and parsing would fail, showing the string is not in the language.

---

2025 Past Paper MCQs (Part-I):

1. What is the role of parser?

   A) To check logical errors B) To find syntax errors C) To identify run-time errors D) None of these

   Why: The parser (syntax analyzer) checks the token stream against the language's grammar and is what actually detects and reports syntax errors.

2. Which optimization method involves minimizing the memory access count in a program?

   A) Constant folding B) Register allocation C) Instruction scheduling D) None of these

   Why: Keeping frequently-used values in registers instead of memory (register allocation) directly cuts the number of load/store memory accesses.

3. Which phase of compiler is responsible for abstract syntax tree (AST) generation?

   A) Syntax analysis B) Semantic analysis C) Lexical analysis D) None of these

   Why: The syntax analysis (parsing) phase builds the parse tree, which is then simplified into the abstract syntax tree (AST), from the token stream according to the grammar.

---

2024

Q8. Regex for Date Formats

Appeared: 2024, Q8(a), 5 marks

Write Regular Expression(s) for the following (5 each): For date Format of standard e.g. (10.03.2024 | 12/30/2023| 01/01/2022)

Solution:

^\d{1,2}[./]\d{1,2}[./]\d{4}$

This matches two 1-2 digit numeric groups (covering day/month values from 1-31 in either order, since the examples mix dd.mm.yyyy and mm/dd/yyyy formats) separated by either a dot or a slash, followed by a 4-digit year. A stricter, range-validated version enforcing day 01-31 and month 01-12 explicitly would be: ^(0[1-9]|[12]\d|3[01])[./](0[1-9]|1[0-2])[./]\d{4}$

---

Q9. Regex for URLs

Appeared: 2024, Q8(b), 5 marks

Write a Regular Expression that will match URL e.g. (http://example.edu.pk)

Solution:

^https?://[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}(/[^\s]*)?$

This matches an optional 's' after http (for https), followed by "://", a domain name made of letters/digits/dots/hyphens ending in a top-level domain of at least 2 letters, and an optional path component after a trailing slash.

---

Q10. Regex for IP Addresses

Appeared: 2024, Q8(c), 5 marks

Write a Regular Expression that will match an IP address. e.g. 192.168.0.1

Solution:

^((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$

Each of the four dot-separated octets is constrained to the valid range 0-255 using the alternation: 250-255 (25[0-5]), 200-249 (2[0-4][0-9]), or 0-199 (a 1-3 digit number not starting improperly, [01]?[0-9][0-9]?), giving a properly range-validated IPv4 address matcher.

---

Q11. Regex for Email Addresses

Appeared: 2024, Q8(d), 5 marks

Write a Regular Expression that will match an email address. e.g. (abc@example.com)

Solution:

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

This matches one or more allowed local-part characters (letters, digits, dot, underscore, percent, plus, hyphen), followed by '@', a domain name of letters/digits/dots/hyphens, and a top-level domain of at least 2 letters.

---

2024 Past Paper MCQs (Part-I):

1. When compiled, which of the following class of statement often yields no executable code?

   A) Assignment statement B) Structural statements C) Input and output statements D) None of these

   Why: Structural/declarative statements (e.g. variable or type declarations) only tell the compiler about the program's structure — they don't translate into runnable instructions the way assignment or I/O statements do.

2. A high-level language compiler that runs on one computer and generates code for another is known as:

   A) One pass compiler B) Multipass compiler C) Cross compiler D) None of these

   Why: A cross compiler executes on one host machine but produces object code meant to run on a different target machine/architecture.

3. Compiler can check error.

   A) Syntax B) Content C) Logical D) None of these

   Why: Compilers detect syntax (and some static semantic/type) errors at compile time; logical errors only show up as wrong behavior at runtime, which the compiler cannot check.

---

2023

Q12. FA Recognizing '001' as a Substring

Appeared: 2023, Q7(a), 8 marks

Design and draw a finite automaton to recognize the regular language of all strings that contain the string '001' as a substring.

Solution:

This can be recognized by a DFA that tracks how much of the pattern "001" has been matched so far as a suffix of the input read:

States: q0 (no progress / initial), q1 (matched "0"), q2 (matched "00"), q3 (matched "001" - accepting, and absorbing since once "001" appears anywhere, the string is accepted regardless of what follows).

Transition table:

• q0 -0→ q1, q0 -1→ q0
• q1 -0→ q2, q1 -1→ q0
• q2 -0→ q2, q2 -1→ q3
• q3 -0→ q3, q3 -1→ q3 (self-loop on both symbols; once accepted, it stays accepted)

Start state: q0. Accepting state: {q3}. Any input string that at any point produces the subsequence 0,0,1 causes the automaton to reach q3 and remain there, so it correctly accepts exactly the strings containing "001" as a substring.

---

Q13. Extracting Q, Σ, q0, F, δ from a State Diagram

Appeared: 2023, Q7(b), 6 marks

Consider the following state diagram and extract the standard information, i.e., Q, Σ, q0, F and δ. (Diagram shows states a, b and a double-circled final state; arrows: self-loop 0 on a, a->b labeled 1, a curved top arc labeled 1 from a to the final state, b->final labeled 0, and a self-loop labeled 1 on the final state.)

Solution:

Reading the given diagram (states a, b, and a double-circled accepting state, call it f):

Q = {a, b, f}
Σ = {0, 1}
q0 = a  (the state with the initial incoming arrow)
F = {f}  (the double-circled state)

δ (transition function), read off the arrows shown:

• δ(a, 0) = a (self-loop on a)
• δ(a, 1) = {b, f} (the straight arrow a->b, and the curved top arc directly from a to f, both labeled 1 - making this an NFA)
• δ(b, 0) = f
• δ(f, 1) = f (self-loop on f)

This machine is a Non-deterministic Finite Automaton (NFA), since state a has two possible transitions on input symbol 1 (to b and to f).

---

Q14. Loop Optimization Techniques

Appeared: 2023, Q7(c), 6 marks

How would you optimize a loop? Describe the techniques briefly.

Solution:

Common loop optimization techniques used by compilers:

1. Loop-invariant code motion: moving computations that produce the same result every iteration (do not depend on the loop variable) outside the loop body, so they execute only once instead of n times.

2. Strength reduction: replacing expensive operations inside a loop with cheaper equivalent ones, e.g., replacing repeated multiplication i*4 in successive iterations with a running addition of 4 each iteration.

3. Induction variable elimination: removing redundant loop-control variables that are simple linear functions of the main loop counter, keeping only the necessary one.

4. Loop unrolling: replicating the loop body multiple times per iteration to reduce the relative overhead of loop-control instructions (test/increment/branch) and enable more instruction-level parallelism.

5. Loop fusion/fission: merging (fusion) adjacent loops with the same iteration range to reduce loop overhead and improve cache locality, or splitting (fission) a large loop into smaller ones when it improves cache behavior or enables further optimization/parallelization.

6. Common subexpression elimination inside loops: computing a repeated expression once and reusing the stored result rather than recomputing it every iteration.

---

Q15. Syntax Tree for a While/If/Else Program

Appeared: 2023, Q8(a), 8 marks

Discuss the role of Syntax Tree in representing formal text structure. Develop a Syntax Tree structure for the following piece of code: while b ≠ 0 if a > b a = a - b; else b = b - a; return a;

Solution:

A syntax tree (abstract syntax tree, AST) represents the hierarchical grammatical structure of source code, with each internal node representing an operator/language construct and each leaf representing an operand/identifier/literal. Unlike a parse tree, it omits purely syntactic details (parentheses, keywords used only for grouping) and captures only the meaningful structure needed for further processing (e.g., by a compiler for type-checking, optimization, or code generation).

Syntax tree for the given code:
              (sequence)
              /        \
         (while)      (return)
         /     \           |
     (!=)     (if)         a
     /  \    /   |   \
    b    0 (>) (then) (else)
          / \    |       |
         a   b (assign) (assign)
              /  \       /  \
             a   (-)    b   (-)
                 / \        / \
                a   b      b   a
The root sequences the while-loop followed by the return statement. The while node has a condition child (b != 0) and a body child (the if-statement). The if node has a condition (a > b), a then-branch (a = a - b), and an else-branch (b = b - a); each assignment is itself a small subtree with the '=' operator, the left-hand variable, and a '-' subtraction subtree on the right.

---

Q16. Constant Folding with Pseudocode

Appeared: 2023, Q8(b), 6 marks

Describe your understanding on Constant Folding using a brief pseudo code.

Solution:

Constant folding is a compiler optimization technique that evaluates expressions whose operands are all known constants at compile time, replacing the entire expression with its precomputed result, so that the computation does not need to be repeated every time the program runs.

// Before constant folding
x = 3 + 4 * 2;
y = x * (10 - 10);

// After constant folding (done by the compiler)
x = 11;      // 4*2=8, then 3+8=11, computed once at compile time
y = x * 0;   // 10-10 folded to 0
By performing this evaluation once during compilation instead of on every execution, constant folding reduces the number of run-time instructions, improving performance without changing the program's observable behavior; it is often combined with constant propagation, which substitutes known constant variable values into later expressions to expose further folding opportunities.

---

2022

Q17. FA for Strings Starting and Ending with 0

Appeared: 2022, Q8(a), 8 marks

Draw a finite automaton over ∑ = {0, 1} that accepts all binary strings starting and ending with 0 (single-0 string counts).

Solution:

We need a DFA that accepts strings whose first symbol is 0 AND whose last symbol is 0 (a single "0" satisfies both and must be accepted).

States: q0 (start, nothing read yet), qA (started with 0, currently ends in 0 - accepting), qB (started with 0, currently ends in 1 - non-accepting), qD (started with 1 - dead/trap state, can never be accepted since the first symbol was 1).

Transition table:

• q0 -0→ qA (accept immediately: a single "0" both starts and ends with 0)
• q0 -1→ qD
• qA -0→ qA
• qA -1→ qB
• qB -0→ qA
• qB -1→ qB
• qD -0→ qD
• qD -1→ qD

Start state: q0. Accepting state: {qA}. Any string is accepted if and only if it begins with 0 (reaching qA or qB, never qD) and its last transition lands on qA (i.e., the last symbol read was 0).

---

Q18. Regex for Strings Starting with 101, Ending with 110

Appeared: 2022, Q8(b), 6 marks

Write a regular expression over ∑ = {0, 1} to represent a set of strings that begin with 101 and end with 110.

Solution:

Regular expression: 101(0|1)*110

This requires the string to start with the literal prefix "101", then allows any (possibly empty) sequence of 0s and 1s in the middle via (0|1), and requires the string to end with the literal suffix "110". The minimum-length string satisfying this is "101110" (length 6), obtained when the middle (0|1) part matches the empty string - here the prefix "101" and suffix "110" simply concatenate directly.

---

Q19. CFG for 0^a 1^b 0^c where a+c=b

Appeared: 2022, Q8(c), 6 marks

Write a Context-Free Grammar (CFG) over ∑ = {0, 1} for the language of all binary strings of the form 0^a 1^b 0^c where a+c=b.

Solution:

Since b = a+c, the string 0^a 1^b 0^c can be rewritten as 0^a 1^(a+c) 0^c = (0^a 1^a)(1^c 0^c), i.e., the concatenation of a block generating equal 0s then 1s, followed by a block generating equal 1s then 0s. This gives a simple two-part grammar:

S -> X Y
X -> 0 X 1 | epsilon      (generates 0^a 1^a)
Y -> 1 Y 0 | epsilon      (generates 1^c 0^c)

Derivation check: S => XY => (0^a 1^a)(1^c 0^c) = 0^a 1^(a+c) 0^c, which is exactly 0^a 1^b 0^c with b=a+c, for any a,c >= 0. For example, with a=2, c=1 (so b=3): X derives "0011", Y derives "10", giving S => "0011" + "10" = "001110" = 0^2 1^3 0^1, matching the required pattern.

---

2021

Q20. NFA to DFA — Subset Construction

Appeared: 2021, Q6(a), 8 marks

Convert following NFA to DFA:

Solution:

Reading the NFA from the figure: states q0 (start), q1, q2 (accepting, double circle); alphabet {0,1}. Transitions: δ(q0,0)={q0}, δ(q0,1)={q1}; δ(q1,0)={q1}, δ(q1,1)={q2}; δ(q2,0)={q1,q2} (nondeterministic branch), δ(q2,1)={q1}.
Applying the subset construction:
Start state A = {q0}.
A={q0}: on 0 → {q0}=A; on 1 → {q1}=B (new)
B={q1}: on 0 → {q1}=B; on 1 → {q2}=C (new)
C={q2}: on 0 → {q1,q2}=D (new); on 1 → {q1}=B
D={q1,q2}: on 0 → δ(q1,0)∪δ(q2,0) = {q1}∪{q1,q2} = {q1,q2}=D; on 1 → δ(q1,1)∪δ(q2,1) = {q2}∪{q1} = {q1,q2}=D

Resulting DFA states: A={q0} (start), B={q1}, C={q2}, D={q1,q2}. Final (accepting) states: any DFA state containing q2, i.e. C and D. DFA transition table:

---

Q21. Top-Down Parse Tree for w = cad

Appeared: 2021, Q8(a), 4 marks

Consider the grammar S → cAd, A → a b | a, construct a top-down parse tree for the input string w = cad

Solution:

Leftmost derivation: S ⇒ cAd ⇒ (choosing production A → a) ⇒ cad, which matches w = cad exactly.
Top-down parse tree:
        S
      / | \
     c  A  d
        |
        a
The root S expands via S → cAd into the three children 'c', 'A', and 'd'; the non-terminal A then expands via the production A → a into the single leaf 'a'. Reading the leaves left to right gives exactly 'c a d' = w.

---

Q22. Ambiguous or Unambiguous Grammar?

Appeared: 2021, Q8(b), 4 marks

Is the above given grammar ambiguous or unambiguous? Justify your answer.

Solution:

The grammar is UNAMBIGUOUS. A grammar is ambiguous only if some string it generates has two or more distinct parse trees (or leftmost derivations). Here, S has only one production (S → cAd), and A has exactly two alternative productions producing two entirely distinct, non-overlapping terminal strings: 'a' and 'ab'. For any string the grammar generates — 'cad' (via A → a) or 'cabd' (via A → ab) — there is exactly ONE way to choose which A-production applies, since the two alternatives never produce the same string. Hence every derivable string has a unique parse tree, and the grammar is unambiguous.

---

Q23. CFG vs Regular Expression

Appeared: 2021, Q8(c), 4 marks

Write similarities and differences of CFG and regular expression.

Solution:

Similarities: both are formal notations used to define/specify formal languages; every regular language expressible by a regular expression can ALSO be expressed by a context-free grammar (regular languages are a proper subset of context-free languages); both are used together in compiler construction — regular expressions for lexical analysis (tokenizing) and CFGs for syntax analysis (parsing). Differences: a regular expression can only describe REGULAR languages, recognisable by a finite automaton with no auxiliary memory, and cannot express nested or recursively-balanced structures (e.g. matched parentheses, palindromes). A context-free grammar can describe the strictly LARGER class of context-free languages, recognisable by a pushdown automaton equipped with a stack, and CAN express nested/recursive structures. Structurally, regular expressions are built from terminals using operators (concatenation, union '|', Kleene star '*'), whereas CFGs use recursive production rules over non-terminal and terminal symbols.

---

Q24. Grammar Where Every 0 Is Followed by a 1

Appeared: 2021, Q8(d), 4 marks

Design grammar for the following language: "The set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1".

Solution:

Grammar (start symbol S):
S → 1S | 01S | ε
Reasoning: the empty string vacuously satisfies the condition (no 0 exists to violate it), so S → ε is allowed. A standalone '1' can always be generated (S → 1S) since 1s impose no constraint. Crucially, every '0' can ONLY be generated together with a '1' immediately after it, via S → 01S — there is no production that produces a lone '0' or a '0' at the very end of the string, so '00' and a trailing '0' are both structurally impossible to derive. Example derivations: S ⇒ 01S ⇒ 011S ⇒ 011 (via S→1S then ε) generates '011'; S ⇒ 1S ⇒ 101S ⇒ 1011 generates '1011' — both satisfy the condition that every 0 is immediately followed by a 1.

---

2020

Q25. State Transition Table from a Graph

Appeared: 2020, Q7(b), 5 marks

Create State Transition Table from the following graph

Solution:

Reading the transitions shown in the figure (states q0-q5): δ(q0,a)=q1, δ(q0,b)=q1; δ(q1,a)=q2, δ(q1,b)=q3; δ(q2,a)=q4, δ(q2,b)=q4; δ(q3,a)=q2, δ(q3,b)=q4; δ(q4,a)=q5, δ(q4,b)=q5; δ(q5,a)=q5, δ(q5,b)=q5 (self-loop). State transition table:

---

Q26. FSA Accepting a Fixed Set of Strings

Appeared: 2020, Q7(c), 4 marks

Draw Finite State Automata which accepts following input. i. JIM ii. JMI iii. JJIIM iv. JJMMII

Solution:

Since this is a specific FIXED finite set of four strings (not a general repeating pattern), it is automatically a regular language (every finite language is regular) and can be accepted by a simple 'trie-shaped' DFA: a distinct path of states from the start state q0 spells out each string, sharing common prefixes, with a unique accepting state at the end of each string's path, and an implicit dead/trap state for any other symbol/continuation:
q0 --J--> q1
q1 --I--> q2 --M--> [F1] (accepts JIM)
q1 --M--> q3 --I--> [F2] (accepts JMI)
q1 --J--> q4 --I--> q5 --I--> q6 --M--> [F3] (accepts JJIIM)
q4 --M--> q7 --M--> q8 --I--> q9 --I--> [F4] (accepts JJMMII)
Every other input symbol from any state goes to a non-accepting dead state. This trie automaton accepts exactly the four given strings and nothing else.

---

Q27. Validating Inputs Against a Given FSM

Appeared: 2020, Q7(d), 6 marks

Determine which of these inputs are valid for the FSM shown below: i. aaaaa ii. ababa iii. abcabc iv. abccba v. acbcd vi. acbcdcd

Solution:

Reading the transitions shown in the figure (states S1 start, S2, S3, S4; alphabet {a,b,c}; self-loop 'a' on S2): δ(S1,a)=S2, δ(S1,b)=S3, δ(S2,a)=S2 (self-loop), δ(S2,b)=S4, δ(S3,a)=S1, δ(S3,c)=S4, δ(S4,c)=S2. (S4 assumed to be the accepting state.)
i. aaaaa: S1-a->S2-a->S2-a->S2-a->S2-a->S2 → ends at S2 (not accepting) → INVALID.
ii. ababa: S1-a->S2-b->S4-a-> undefined (S4 has no transition on 'a') → dead → INVALID.
iii. abcabc: S1-a->S2-b->S4-c->S2-a->S2-b->S4-c->S2 → ends at S2 → INVALID.
iv. abccba: S1-a->S2-b->S4-c->S2-c-> undefined (S2 has no transition on 'c') → dead → INVALID.
v. acbcd: contains 'd', which is not in the machine's input alphabet {a,b,c} → INVALID.
vi. acbcdcd: also contains 'd' → INVALID.
(Answer given based on the transition structure read from the figure; the key general technique is to trace each input symbol-by-symbol from the start state and check whether it ends in an accepting state without ever hitting an undefined transition or an out-of-alphabet symbol.)

---

2019

Q28. Major Steps in Code Generation

Appeared: 2019, Q8(a), 10 marks

Write down the major steps involved in code generation.

Solution:

Code generation is the final phase of a compiler, converting the optimized intermediate representation (IR) into target machine/assembly code. Major steps:

1. Input acquisition — take the intermediate code (e.g. three-address code) and the symbol table (with type and address information) as input.
2. Instruction selection — choose appropriate target-machine instructions to implement each IR operation, often using tree/DAG pattern matching against available instruction templates.
3. Register allocation and assignment — decide which values are kept in the limited set of physical registers versus spilled to memory, and assign specific registers to variables/temporaries.
4. Instruction ordering/scheduling — sequence the chosen instructions to respect data dependencies while exploiting pipeline parallelism and minimizing stalls.
5. Address assignment — allocate storage locations (stack offsets, static addresses) for variables and temporaries not held in registers.
6. Peephole optimization — a final local pass that scans short instruction sequences and replaces them with more efficient equivalents (removing redundant loads/stores, strength reduction, etc.).
7. Target code emission — output the final assembly or machine code.

---

Q29. Loop Optimization Techniques

Appeared: 2019, Q8(b), 5 marks

How would you optimize a loop? Describe the techniques briefly.

Solution:

Common loop-optimization techniques:

• Code motion (loop-invariant code motion) — move computations whose result does not change across iterations to just before the loop, so they execute once instead of every iteration.
• Strength reduction — replace expensive operations with cheaper equivalents inside the loop, e.g. replacing i*4 with repeated addition, or multiplication with shifts.
• Induction-variable elimination — remove redundant variables that merely track the loop counter in a derived way, expressing them in terms of the primary counter or eliminating them entirely.
• Loop unrolling — replicate the loop body multiple times per iteration to reduce branch/counter overhead and expose more instruction-level parallelism.
• Loop fusion/jamming — merge adjacent loops with the same iteration range into a single loop to reduce loop-control overhead and improve cache locality.
• Loop-invariant boundary/condition simplification — hoist parts of the loop test that do not change.

---

Q30. Machine-Dependent vs Machine-Independent Optimization

Appeared: 2019, Q8(c), 5 marks

Differentiate machine-dependent optimization and machine-independent optimization.

Solution:

Machine-independent optimization works on the intermediate representation and improves the code without any knowledge of the target machine's architecture — it would give the same benefit regardless of which CPU the code eventually runs on. Examples: constant folding, dead-code elimination, common sub-expression elimination, and loop optimizations such as code motion. Machine-dependent optimization requires knowledge of the target machine's specific architecture — its register set, addressing modes, and instruction set — and is applied during/after code generation. Examples: register allocation/assignment, instruction selection tuned to the CPU's instruction set, and peephole optimization exploiting machine-specific instruction idioms. In short: machine-independent optimizations are portable and applied earlier (on IR); machine-dependent optimizations are architecture-specific and applied later (on/near the generated target code).

---

2018

Q31. Lexers vs Parsers

Appeared: 2018, Q8(a), 5 marks

What is the difference between lexers and parsers?

Solution:

A Lexer (Lexical Analyzer / Scanner) is the first phase of a compiler; it reads the raw source code character-by-character and groups characters into meaningful 'tokens' (keywords, identifiers, literals, operators, punctuation) based on the language's lexical rules, which are typically specified using regular expressions and implemented internally via finite automata (DFAs). It discards irrelevant content like whitespace and comments, and can detect lexical errors (e.g. an invalid character or malformed token).

A Parser (Syntax Analyzer) is the second phase; it takes the stream of tokens produced by the lexer and checks whether they form a syntactically valid program according to the language's Context-Free Grammar, building a parse tree or Abstract Syntax Tree (AST) representing the program's grammatical structure. It detects syntax errors (e.g. a missing semicolon, mismatched parentheses, invalid statement structure).

Key difference: the lexer operates on individual characters to produce tokens (a 'flat'/linear recognition task, handled by finite automata / regular languages), whereas the parser operates on the sequence of tokens to verify and structure the overall grammatical relationship between them (a 'hierarchical' recognition task, requiring the greater expressive power of context-free grammars and pushdown automata, since regular languages/finite automata cannot handle arbitrarily nested structures like matched parentheses).

---

Q32. BNF Grammar for Palindromes

Appeared: 2018, Q8(b), 5 marks

Write a grammar (BNF) for the language of palindromes.

Solution:

For palindromes over the alphabet {a, b} (strings that read the same forwards and backwards), a context-free grammar in BNF:

<Palindrome> ::= 'a' <Palindrome> 'a'
             | 'b' <Palindrome> 'b'
             | 'a'
             | 'b'
             | ''      (empty string)

Explanation: the grammar builds a palindrome outward from its center. The base cases are the empty string (even-length center) and a single character 'a' or 'b' (odd-length center). The recursive rules wrap a matching character on BOTH the left and right sides of an already-valid (shorter) palindrome, guaranteeing the result reads identically forwards and backwards.

Example derivations: 'aba' via -> aa -> a(b)a = 'aba'. 'abba' via -> aa -> a(b)a... actually for 'abba': -> aa -> a(bb)a, using the empty-string base case for the inner , giving a(b()b)a = 'abba'. This grammar is not regular (cannot be expressed by a finite automaton) because it requires matching an unbounded number of characters on the outside with their mirror on the inside - it requires the greater power of a context-free grammar (recognized by a pushdown automaton with a stack).

---

Q33. DFA for L² (Language Squared)

Appeared: 2018, Q8(c), 5 marks

Here DFA is given for the language L find the DFA for L^2 (squared/concatenated with itself). [DFA: start q0 (self-loop on 'a'), q0 -b→ q1 (final, double circle), q1 -a,b→ q2 (trap), q2 self-loops on a,b]

Solution:

First, identify L: from the given DFA (q0 start, self-loop on 'a'; q0 -b→ q1 which is the sole accepting state; from q1, any symbol a or b goes to trap state q2; q2 self-loops on a,b forever, non-accepting), the accepted language is L = { a^n b : n >= 0 } - i.e., zero or more 'a's followed by exactly one 'b', and nothing else (any character after that single 'b' sends the automaton into the non-accepting trap state).

L^2 = L concatenated with L = { a^n b a^m b : n, m >= 0 } - strings consisting of some a's, a b, then more a's, then a final b, with nothing else allowed (exactly two b's total).

DFA for L^2 (concatenation automaton - essentially two copies of the original DFA chained together): States: r0 (start), r1 (intermediate, after first 'b'), r2 (final/accepting, after second 'b'), trap (dead state).

Transitions:

• r0 -a→ r0 (self-loop, consuming leading a's)
• r0 -b→ r1 (first 'b' seen)
• r1 -a→ r1 (self-loop, consuming a's between the two b's)
• r1 -b→ r2 (second 'b' seen - ACCEPT)
• r2 -a→ trap
• r2 -b→ trap
• trap -a,b→ trap (dead state, non-accepting)

Only r2 is a final/accepting state. This DFA accepts exactly strings of the form a^n b a^m b, matching L^2.

---

Q34. Converting a DFA to a Regular Expression

Appeared: 2018, Q8(d), 5 marks

Convert the following DFA to a RE: [states 1 (start) through 5 (final), forward edges labelled 3 advancing one state at a time (1-2-3-4-5), and additional edges labelled 6 skipping ahead one extra state (1-3, 2-4, 3-5)]

Solution:

Note: the transition diagram in the original paper uses curved/overlapping arcs that are difficult to reproduce exactly from the scanned text; the derivation below uses the most natural reading of the figure - symbol '3' advances the state machine forward by exactly one position (1->2->3->4->5) and symbol '6' advances it forward by exactly two positions (1->3, 2->4, 3->5), with state 1 as the start state and state 5 as the only accepting (final) state, and no edges going backward or looping.

Since this is a simple forward-only DAG (no cycles), applying state elimination (Arden's method) reduces to directly enumerating every path from state 1 to state 5, where a '3'-edge contributes a 'weight' of 1 step and a '6'-edge contributes a weight of 2 steps, and any valid path's step-weights must sum to exactly 4 (the total distance from state 1 to state 5).

Enumerating all sequences of steps (each step being '3', weight 1, or '6', weight 2) that sum to 4:

• 1+1+1+1 -> the string '3333'
• 1+1+2 (in the three possible orders) -> '3336', '3363', '3633'
• 2+2 -> the string '66'

So the resulting regular expression is:

RE = 3333 + 3336 + 3363 + 3633 + 66

This captures every distinct path (sequence of transition labels) that starts at state 1 and ends at the accepting state 5, which is exactly what state elimination on this acyclic diagram would also produce, since with no cycles present, the general state-elimination/Arden's-lemma procedure reduces to plain enumeration of all source-to-sink paths.

---

2017

Q35. Machine vs Low-Level vs High-Level Languages

Appeared: 2017, Q3(a), 8 marks

Three types of languages exist for use in programming of computers, Machine, Low Level and High Level languages. Elucidate on these three types, giving details of the conversion process between Low Level and High Level language into Machine language.

Solution:

Machine Language: the lowest-level language, consisting of raw binary opcodes (0s and 1s) directly understood and executed by the CPU; it is specific to a particular processor architecture and extremely tedious/error-prone for humans to write.

Low-Level Language (Assembly Language): uses short mnemonics (e.g. MOV, ADD, JMP) that map almost one-to-one to machine instructions, giving fine control over hardware but still being architecture-specific and harder to write than high-level code.

High-Level Language (e.g. C++, Java, Python): uses English-like syntax and abstracts away hardware details (registers, memory addresses), making programs portable, easier to write, read, and maintain, at some cost of direct hardware control.

Conversion process:

• Assembly to Machine code: an Assembler translates assembly mnemonics directly into machine code, essentially a one-to-one/simple mapping, producing object code.
• High-Level to Machine code: a Compiler performs several phases - lexical analysis (tokenizing), syntax analysis (parsing into a parse tree per the language's grammar), semantic analysis (type-checking), intermediate code generation, code optimization, and finally target code generation (assembly or machine code), which is then assembled and linked into an executable. Alternatively, an Interpreter directly executes the high-level source (or an intermediate bytecode) statement by statement without producing a separate machine-code file.

---

Q36. Syntax Error Handling — Lexer and Parser Roles

Appeared: 2017, Q7(a), 8 marks

The handling of syntax errors involves the use of parser and the lexical analyzer. Comment on its functioning.

Solution:

The Lexical Analyzer (Scanner) reads the source program character-by-character and groups them into tokens (keywords, identifiers, operators, literals) based on the language's lexical rules (regular expressions/finite automata). It can detect lexical errors, such as illegal characters or malformed tokens (e.g. an unterminated string literal), and typically reports them and attempts simple recovery (e.g. skipping the bad character) so scanning can continue.

The Parser (Syntax Analyzer) takes the token stream from the lexer and checks it against the language's context-free grammar, building a parse tree/AST. When a sequence of tokens does not conform to any valid grammar production, a syntax error is detected (e.g. a missing semicolon, unbalanced parentheses, misplaced keyword).

Error-handling/recovery strategies used by parsers:

• Panic mode: the parser discards tokens one at a time until a token from a predefined synchronizing set (e.g. ';', '}') is found, then resumes parsing - simple but may skip other real errors.
• Phrase-level recovery: the parser performs local correction (inserting/deleting/replacing a token) at the point of error to continue parsing.
• Error productions: the grammar is augmented with rules that explicitly anticipate common errors.
• Global correction: computes the minimal sequence of edits needed to transform the erroneous input into a valid program (theoretically ideal but computationally expensive, rarely used in practice).

Together, the lexer and parser cooperate so that a single glitch does not halt compilation - both aim to detect as many genuine errors as possible in one pass while avoiding cascading false errors.

---

Q37. Top-Down vs Bottom-Up Parsing

Appeared: 2017, Q7(b), 6 marks

Using a suitable example, compare the operation of a top-down and a bottom-up Parser based compiler.

Solution:

Top-down Parsing: begins construction of the parse tree from the root (start symbol) and works down toward the leaves (input tokens), trying to derive the input string by repeatedly expanding non-terminals using the grammar's productions, guessing/predicting which production to apply next (e.g. Recursive-Descent parsers, LL parsers). It matches the leftmost derivation of the grammar.

Bottom-up Parsing: begins from the input tokens (leaves) and works upward, repeatedly identifying substrings matching the right-hand-side of a production and reducing them to the corresponding non-terminal, until the whole input reduces to the start symbol (e.g. Shift-Reduce parsers, LR parsers). It matches the rightmost derivation in reverse.

Example with grammar E -> E + T | T, T -> id, for input 'id + id':

• Top-down: start with E, expand to E + T, expand E again to T + T, then T -> id gives 'id + T', then T -> id gives 'id + id' - matching the input by predicting expansions from the start symbol downward.
• Bottom-up: start with tokens 'id + id'; reduce first 'id' to T (T->id), then to E (E->T); shift '+'; reduce second 'id' to T; finally reduce 'E + T' to E - building up from the leaves to the root.

Top-down parsers (LL) are simpler to hand-write but cannot handle left-recursive grammars directly; bottom-up parsers (LR) are more powerful (handle a larger class of grammars, including left-recursion) but are more complex to construct, typically via parser-generator tools (e.g. YACC/Bison).

---

Q38. Loop Optimization vs Peephole Optimization

Appeared: 2017, Q7(c), 6 marks

Explain the two different methods of code optimization that is Loop optimization and Peephole optimization by giving a suitable example.

Solution:

Loop Optimization: since loops are executed repeatedly, optimizing them yields the greatest overall performance benefit. Common techniques:

• Code motion (loop-invariant code motion): move computations that don't change across iterations outside the loop.

Example: for(i=0;i<n;i++){ x = y+1; a[i]=xi; } → x=y+1; for(i=0;i<n;i++){ a[i]=xi; } Here 'x=y+1' is invariant and computed only once instead of n times.

• Strength reduction: replace an expensive operation with a cheaper equivalent one, e.g. replacing i*4 (multiplication) inside a loop with repeated addition of 4 (an accumulator), since addition is cheaper than multiplication.
• Induction variable elimination: remove redundant loop-counter-derived variables.

Peephole Optimization: examines a small, sliding 'window' (peephole) of a few consecutive generated instructions at a time and replaces them with a shorter/faster equivalent sequence, applied directly to the generated (often target/assembly) code. Example: MOV R1, a MOV a, R1 The second instruction is redundant (storing a value right back to where it came from) and can be eliminated by the peephole optimizer. Another example: replacing 'x = x + 0;' or 'x = x * 1;' with nothing (removing no-op arithmetic), or combining two consecutive jumps into one.

Loop optimization targets algorithmic-level redundancy across iterations at a higher (often intermediate-code) level, while peephole optimization targets small, local, redundant instruction sequences at the final code-generation level.

---

Q39. Short Note — Intermediate Code Generation

Appeared: 2017, Q8(e), 5 marks

Write short notes on any FOUR of the following (5 each): (e) Intermediate Code Generation

Solution:

Intermediate Code Generation is a phase of compilation that occurs after semantic analysis and before final target code generation. The compiler translates the syntax tree/parse tree into an intermediate representation (IR) that is independent of both the source high-level language and the target machine.

Purpose:

• Portability: the same front-end (lexer, parser, semantic analyzer) can target multiple machine architectures by writing different back-ends that consume the same IR, and the same back-end can support multiple source languages.
• Optimization: many optimizations (constant folding, common sub-expression elimination, loop optimizations) are easier to perform on a simple, uniform IR than directly on the parse tree or final machine code.

Common IR forms:

• Three-Address Code (TAC): each statement has at most one operator on the right and involves at most three addresses/operands, e.g. t1 = b * c; t2 = a + t1; for the expression a + b*c.
• Postfix (Reverse Polish) notation: e.g. a b c * +.
• Syntax trees / DAGs (Directed Acyclic Graphs): tree/graph representation that can also expose common sub-expressions for reuse.

After intermediate code is generated (and optionally optimized), the code generator translates it into the final target machine/assembly code.

---

2016

Q40. Compilation Pipeline: Source to Executable (C++)

Appeared: 2016, Q7(a), 5 marks

Draw a diagram that illustrates the process of translating a C++ source file into an executable file. Give example of each phase depicted in your diagram of compilation process.

Solution:

Compilation pipeline (source to executable):

Source Code (main.cpp)
   |  Preprocessor  (expands #include <iostream>, #define macros, conditional compilation)
   v
Expanded Source Code (main.i)
   |  Compiler proper (lexical analysis -> syntax analysis -> semantic analysis -> code generation)
   v
Assembly Code (main.s)
   |  Assembler (translates mnemonics like MOV, ADD into machine opcodes)
   v
Object Code (main.o / main.obj) -- relocatable machine code, unresolved external references
   |  Linker (combines object files with library code, e.g. iostream library object code; resolves external symbols like cout, resolves addresses)
   v
Executable File (main.exe / a.out)
   |  Loader (loads the executable into main memory and starts execution)
   v
Program Execution

Example: #include <iostream> is resolved by the preprocessor; cout << x; is parsed/type-checked by the compiler; cout calls become CALL instructions resolved by the linker against the C++ standard library.

---

Q41. Compiler vs Interpreter vs Assembler

Appeared: 2016, Q7(b), 5 marks

Compare and contrast among compiler, interpreter and assembler.

Solution:

Compiler: translates an entire high-level-language source program into machine code (or object code) in one pass before execution; produces a standalone executable; execution is fast since translation happens only once, but the whole program must compile before any part runs and errors are reported after full translation. Example: g++ for C++.

Interpreter: translates and executes a high-level program statement-by-statement at run time, without producing a separate executable; execution is generally slower (translation overhead repeats every run/every loop iteration) but allows immediate feedback and easier debugging, and one erroneous statement doesn't block execution of statements before it. Example: Python interpreter.

Assembler: translates low-level assembly language (mnemonics like MOV, ADD that map almost one-to-one to machine instructions) into machine code/object code; it does not need to understand high-level constructs like loops or classes.

Key contrast: a compiler and interpreter both process high-level languages but differ in when/how translation happens (ahead-of-time vs on-the-fly); an assembler processes a fundamentally lower-level language and is used mainly as the back end that a compiler's generated assembly passes through.

---

Q42. Five Properties of Language (English & MiniJava)

Appeared: 2016, Q8(b), 5 marks

Explain five properties of language using the example of English. Explain why a software language like MiniJava meets these properties as well.

Solution:

Five general properties any language (natural or programming) exhibits:

1. Syntax - a set of rules governing how valid sentences/statements are structured. English: subject-verb-object order; MiniJava: statements must follow its grammar, e.g. if (cond) { ... }.
2. Semantics - the meaning conveyed by syntactically valid constructs. English: 'The cat sat' conveys an action; MiniJava: x = x + 1; means increment x's value.
3. Vocabulary/Lexicon - a finite (or generative) set of basic tokens/words the language is built from. English: dictionary words; MiniJava: keywords, identifiers, literals, operators.
4. Compositionality - larger valid expressions are built by combining smaller valid ones according to rules. English: clauses combine into sentences; MiniJava: expressions combine into statements, statements into methods.
5. Ambiguity/context-sensitivity - natural languages can be ambiguous depending on context; well-designed programming languages minimize this through strict formal grammar (though certain constructs like the 'dangling else' still need explicit disambiguation rules).

MiniJava, being a language with a formally defined grammar (BNF), lexicon (tokens), and precise semantics for each construct, satisfies all these properties just as English does, but with much stricter, unambiguous syntax/semantics so it can be mechanically parsed and compiled.

---

Q43. Regex to NFA, Removing Epsilon-Moves

Appeared: 2016, Q8(c), 5 marks

Lexical analysis: Consider the following regular expression r1 = (A | .... | Z) * (0 | .... | 9)*. Describe the language defined by r1 in English. Turn r1 into an equivalent finite automaton. Remove e-moves from the finite automation.

Solution:

Language: r1 = (A|...|Z)(0|...|9) describes all strings consisting of zero or more uppercase letters (A-Z) followed by zero or more digits (0-9) - e.g. '', 'ABC', '123', 'AB12', 'Z9' are all valid; a digit may never appear before a letter.

NFA with epsilon-moves (typical Thompson construction, using two loop-states joined by an epsilon transition): Start state q0 (accepting, for the empty string):

• q0 -A|...|Z→ q0 (self-loop consuming letters)
• q0 -epsilon→ q1
• q1 (accepting) -0|...|9→ q1 (self-loop consuming digits)

Removing the epsilon-move (epsilon-closure elimination): since eps(q0) = {q0,q1}, we merge the transitions of q1 into q0's transition table directly, and make q0 the sole accepting state carrying both loops: Resulting equivalent NFA/DFA without epsilon moves - single state q0 (start, accepting):

• q0 -A|...|Z→ q0
• q0 -0|...|9→ q0

This single-state automaton (a DFA) accepts exactly the language of letters-then-digits strings, since once a digit is seen the letter transitions are simply never used again by any valid string of the language, and self-looping on the same state correctly enforces 'letters can appear anywhere but digits can only follow, never precede, in this collapsed form is only valid because both symbol sets loop on the same state' - equivalently kept as two states q0->q1 (both accepting) with q0 looping on letters, q0 transitioning to q1 on a digit, and q1 looping on digits, is the safer minimal-change epsilon-free version of the original NFA.

---

Q44. Context-Free Grammar (CFG) with Examples

Appeared: 2016, Q8(d), 5 marks

What do you mean by Context Free Grammar (CFG)? Illustrate your answer with examples.

Solution:

A Context-Free Grammar (CFG) is a formal grammar G = (V, T, P, S) where V is a finite set of non-terminal symbols, T is a finite set of terminal symbols, P is a finite set of production rules of the form A -> alpha (where A is a single non-terminal and alpha is any string of terminals/non-terminals - the replacement of A does not depend on surrounding context, hence 'context-free'), and S is the start symbol. CFGs are used to define the syntax of programming languages and are recognized by pushdown automata.

Example 1 - balanced parentheses:
S -> ( S ) S | epsilon
This generates strings like '()', '(())', '()()' - always properly nested/balanced.

Example 2 - simple arithmetic expressions:
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
This generates expressions such as 'id + id * id' and correctly encodes operator precedence (multiplication binds tighter than addition) through the grammar's structure.

CFGs are the backbone of parser generation in compiler construction (e.g. LL and LR parsers), since a compiler's syntax analysis phase checks whether the token stream can be derived from the language's CFG.

---

Frequency Note

Papers reviewed for this topic so far: 2016–2026 (all eleven years of available Section-B Compiler Construction papers). Across these years the recurring sub-areas are: finite automata & regular expressions (DFA/NFA construction, NFA→DFA subset construction, regex↔automaton conversion), grammars (CFG design, BNF, ambiguity, CFG vs regular expression), parsing (top-down vs bottom-up, parse trees, syntax trees), lexical analysis (lexeme/token/pattern, scanning malformed input, lexers vs parsers), translators and the compilation pipeline (compiler vs interpreter vs assembler, phases of compilation), and the back end (code generation steps, register allocation, instruction scheduling, loop/peephole optimization, constant folding). See the full concept breakdown starting at P-I · VI. Compiler Construction for deeper coverage (compiler phases, syntax analysis/parsing, syntax-directed translation, semantic analysis, intermediate code, code optimization).

---

2026 Past Paper MCQs (Part-I)

1. A compiler needs to recognize tokens. Which phase does this?

   A) Syntax Analysis B) Lexical Analysis C) Code Generation D) None of these

   Why: lexical analysis is the first phase of compilation — it scans the source text and groups characters into tokens.

2. What is the advantage of using LL(1) grammars in Syntax Analysis?

   A) More complex parsing B) Predictive parsing with less complexity C) No need for grammar rules D) None of these

   Why: an LL(1) parser can decide which production to apply by looking just one token ahead, avoiding backtracking.

3. What is the difference between Top-down and Bottom-up parsers?

   A) Top-down is always faster B) Bottom-up handles more grammars C) Top-down starts from start symbol D) None of these

   Why: top-down parsing begins at the grammar's start symbol and works down toward the input; bottom-up begins at the input tokens and works up toward the start symbol. (Option B is also often true in practice — LR-family parsers handle a broader class of grammars than LL — but C states the textbook-definitional difference this question is testing.)

4. What do compilers use for recognizing tokens?

   A) Regular expressions B) Context-free grammars C) Machine code D) None of these

   Why: lexical-analysis patterns for tokens (identifiers, numbers, operators) are defined using regular expressions; context-free grammars are used one phase later, in syntax analysis/parsing.