Topic: Theory of Computation
Consider the NFA with epsilon-transitions below, which is meant to accept strings corresponding to a lexical token id. Here the token digit corresponds to the extended regular expression [0-9] and letter corresponds to [a-zA-Z]. In the diagram, a small incoming edge indicates a start state while double circle indicates a final state.
Which of the following extended regular expressions corresponds to the token id?
- A. letter (letter | $digit)^{*}$
- B. (letter digit)* letter
- C. (letter | $digit)^{*}$
- D. letter (letter* | digit*)
Answer: A. letter (letter | $digit)^{*}$
Explanation: The NFA requires the first character to be a 'letter' to reach the accept state. From the accept state, there are epsilon transitions allowing looping through either a 'letter' or a 'digit' any number of times. Thus, the regular expression is `letter (letter | digit)*`, representing typical identifiers in most programming languages.