GATE CS 2023 Q.19: Lexical Analysis

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 [A\text{-}Za\text{-}z] \\ \text{digit} &\rightarrow [0\text{-}9] \\ \text{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 tokens id?

Official answer and solution

Solution

Analyze Thompson's NFA construction for concatenation and Kleene star.

The regular expression is $\text{letter} (\text{letter} \mid \text{digit})^*$ .

It must begin with a transition on $\text{letter}$ from the start state to an intermediate state.
The second part is a Kleene star over the union of $\text{letter}$ and $\text{digit}$ . Thompson's construction for $r^*$ introduces $\epsilon$ -transitions that loop back to the beginning of the sub-expression and allow bypassing via $\epsilon$ to an accepting state.
In Option (C), the start state transitions on $\text{letter}$ to a hub, which connects via $\epsilon$ -transitions to parallel branches for $\text{letter}$ and $\text{digit}$ , with proper feedback loops and exit paths to the final states, precisely implementing the Thompson construction.

Final answer

Option (C)

Common trap

Choosing an automaton that accepts the empty string or allows a digit as the first symbol.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.