The GATE Grind

GATE 2023 CS – Question 19

Compiler Design · Lexical Analysis · 1 mark · Multiple choice

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: letter → [A-Za-z]; digit → [0-9]; id → letter (letter | digit)*. Which one of the following Non-deterministic Finite-state Automata with ε-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

Diagram for GATE 2023 CS question 19
  1. NFA diagram (A)
  2. NFA diagram (B)
  3. NFA diagram (C)
  4. NFA diagram (D)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) NFA diagram (C)

Explanation

An identifier must begin with a letter, followed by any mixture of letters and digits. In C, the first transition consumes a letter and reaches a final state. Its epsilon branches then consume either one letter or one digit and return to that state, allowing arbitrary repetition.

A wrongly accepts the empty string through an epsilon transition. B cannot alternate letters and digits freely after its branch choice. D only repeats letter-digit pairs after the initial letter.

Thus **C** accepts exactly $\mathrm{letter}(\mathrm{letter}|\mathrm{digit})^*$.

More Lexical Analysis questions

All Lexical Analysis questions →