Question

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: \[ \text{letter} \;\;\rightarrow\;\; [A\!-\!Za\!-\!z] \] \[ \text{digit} \;\;\rightarrow\;\; [0\!-\!9] \] \[ \text{id} \;\;\rightarrow\;\; \text{letter (letter | digit)}^* \] 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). 

• A. A
• B. B
• C. C
• D. D

Hint:

Identifiers in most programming languages must start with a letter, followed by letters or digits. This is why the automaton must force a letter first, and only then allow repetition of both letters and digits.
 

Answer 1

The Correct Option is C

Step 1: Understand the regular expression.
The rule for a valid identifier is: \[ \text{id} = \text{letter} \; (\text{letter} \mid \text{digit})^* \] This means:
- The first character must be a letter.
- The subsequent characters (zero or more) can be either letters or digits.

Step 2: Requirements for the NFA.
The NFA must:
1. Start with a transition on a letter.
2. Allow looping transitions (possibly via ε moves) for both letter and digit.
3. Have at least one accepting state that can be reached after consuming the input.

Step 3: Analysis of options.
- Option (A): Does not correctly capture looping behavior for arbitrary sequences of letters and digits.
- Option (B): Splits states but does not enforce the correct structure for \((\text{letter} \mid \text{digit})^*\).
- Option (C): Correctly models:
    • Initial state requires a letter.
    • Then via ε transitions, moves into loops that accept letter or digit.
    • Accepting state reached correctly after any sequence.
- Option (D): Incomplete — does not ensure repetition of letter or digit in the correct manner.

Step 4: Conclusion.
Only Option (C) satisfies the definition of identifiers.

\[ \boxed{\text{The correct NFA is (C).}} \]