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)

The regular expression for a valid identifier is:

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 $\epsilon$-transitions to read either a letter or a digit, and then returns via an $\epsilon$-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 $(\text{letter} \mid \text{digit})^*$.

• Option (B): From the intermediate state, once the machine branches on an $\epsilon$-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 $(\text{letter} \mid \text{digit})^*$.

Therefore, the correct automaton is given by Option (C).