Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: aligned letter & [A-Za-z] \\ digit & [0-9] \\ id & letter (letter digit)* aligned 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) A) B) C) D)

Official answer: C) . Explanation: The regular expression for a valid identifier is: id = letter(letter digit)* To accept strings belonging to this language: 1. An identifier must start with a letter. The initial transition from the start state on `letter` correctly reaches an accepting (final) state (the double circle). 2. After the first letter, any sequence of letter or digit in any arbitrary order can follow zero or more times, returning to the accepting state after each character. Evaluating the given options: - Option (C): After consuming the first `letter` to reach the final state, it branches non-deterministically via -transitions to read either a `letter` or a `digit`, and then returns via an -transition back to the final state. This allows any arbitrary sequence of letters and digits to be accepted. Thus, (C) is correct. - Option (A): The transitions and structure do not correctly represent (letter digit)*. - Option (B): From the intermediate state, once the machine branches on an -transition into the `letter` state or `digit` state, it can only consume that specific type of character repeatedly via the self-loop. It cannot alternate between letters and digits (e.g., it cannot accept strings like `a1b2`). - Option (D): It enforces a repeating sequence of `letter` followed strictly by `digit`, rather than allowing an arbitrary combination of (letter digit)*. Therefore, the correct automaton is given by Option (C).

Compiler Design · Lexical Analysis

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q19 · MCQ · 1 mark

Consider the following definition of a lexical token `id` for an identifier in a programming language, using extended regular expressions: $\begin{aligned} \text{letter} &\rightarrow [\text{A-Za-z}] \\ \text{digit} &\rightarrow [0\text{-}9] \\ \mathbf{id} &\rightarrow \text{letter} (\text{letter} \mid \text{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)

Select an option to check

Key concept

Lexical Analysis

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Lexical Analysis

Lexical Analysis in GATE CS is consistently tested as a 1-mark foundational topic covering tokenization mechanics, formal automaton models, error classification, and compiler data structure lifecycle. Recent years have shifted from purely definitional phase-matching questions toward practical token segmentation using the maximal munch rule and formal construction of NFA/DFA models from regular expressions.

Full Lexical Analysis guide →

More on Lexical Analysis

All 7 questions on Lexical Analysis →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Compiler Design · Lexical Analysis

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q19 · MCQ · 1 mark

Consider the following definition of a lexical token `id` for an identifier in a programming language, using extended regular expressions: $\begin{aligned} \text{letter} &\rightarrow [\text{A-Za-z}] \\ \text{digit} &\rightarrow [0\text{-}9] \\ \mathbf{id} &\rightarrow \text{letter} (\text{letter} \mid \text{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)

Select an option to check

Key concept

Lexical Analysis

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Lexical Analysis

Full Lexical Analysis guide →

More on Lexical Analysis

All 7 questions on Lexical Analysis →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Lexical Analysis under a clock

More from GATE CSE 2023

More on Lexical Analysis

Step-by-step verified solution

Check you can still solve Lexical Analysis under a clock

More from GATE CSE 2023

More on Lexical Analysis

Step-by-step verified solution

Check you can still solve Lexical Analysis under a clock

More from GATE CSE 2023

More on Lexical Analysis

Share this solution

Step-by-step verified solution

Check you can still solve Lexical Analysis under a clock

More from GATE CSE 2023

More on Lexical Analysis

Share this solution