GATE 2023 CS – Question 19
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)

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})^*$.