Consider the NFA with epsilon-transitions below, which is meant to accept…
2023
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 a double circle indicates a final state.
Which of the following extended regular expressions corresponds to the token id?
- A.
letter (letter | digit)*
- B.
(letter I digit)* letter
- C.
(letter | digit)*
- D.
letter (letter* | digit*)
Attempted by 76 students.
Show answer & explanation
Correct answer: A
The NFA begins with a mandatory transition on 'letter' from the start state to a final state (indicated by the double circle). This implies that every valid identifier must start with a letter. From this final state, there are epsilon transitions leading to two separate paths: one for 'letter' and one for 'digit'. Both paths eventually lead to a state that has an arc returning to the initial final state. This structure allows for zero or more repetitions of either a 'letter' or a 'digit' after the initial character. Therefore, the regular expression corresponds to an initial 'letter' followed by any sequence of 'letters' or 'digits', which is represented as letter (letter | digit)*.