Skip to content
GATEiit

GATE CSE 2023 Q19: ε-NFA accepting identifiers letter (letter | digit)*

Question

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)∗\begin{aligned} \textbf{letter} &\to [\texttt{A-Za-z}] \\ \textbf{digit} &\to [\texttt{0-9}] \\ \textbf{id} &\to \textbf{letter}\ (\textbf{letter} \mid \textbf{digit})^* \end{aligned}

Which one of the following Non-deterministic Finite-state Automata with ϵ\epsilon-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

Four ε-NFAs. (A) start goes to a final state on letter and also by ε; the final state loops on letter and digit. (B) start goes to a final state on letter, which has ε-moves to one final state looping on letter and another final state looping on digit. (C) start goes to a final state on letter; from it ε-moves lead to a letter branch and a digit branch that both rejoin a state with an ε-move back to the final state. (D) start goes to a final state on letter, then letter followed by digit, with an ε-move back to the final state
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2023 final answer key)

Concept used: Thompson-style construction of an ε-NFA for concatenation, union and Kleene star.

First step: Test each automaton on short strings: the empty string, 'a1b', and '1' must be rejected, accepted and rejected respectively.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2023 questions →