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)

four NFA diagrams (A)-(D) with letter, digit and ε transitions.
  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: (A) NFA diagram (A)

Explanation

The correct NFA must first consume a letter and then loop on letter or digit before accepting. Only diagram (A) implements letter(letter|digit)* with proper ε-transitions.