Consider the following definition of a lexical token id for an identifier in a…
2023
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:
letter → [A-Za-z]
digit → [0-9]
id → letter (letter | digit)∗
Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)
Attempted by 133 students.
Show answer & explanation
Answer: The correct automaton is the one that consumes a letter from the start to reach an accepting state, and that accepting state has loops on both letters and digits.
Why this implements the regular expression letter(letter|digit)*:
The transition on a letter from the start enforces that every accepted string begins with a letter (the required leading letter).
A loop on the accepting state labeled with both letters and digits allows any number (including zero) of letters or digits to follow, matching (letter|digit)*.
Because the accepting state is reached only after consuming the first letter, strings that start with a digit or the empty string are not accepted.
Why the other diagrams are incorrect (brief):
A diagram that uses epsilon transitions to bypass the initial-letter requirement can accept the empty string or strings that do not start with a letter; that violates the regex.
A diagram that branches early with epsilon into letter-only and digit-only loops may allow starting with a digit or accepting with no characters consumed, so it does not enforce the required initial letter.
A diagram that enforces a fixed sequence after the first letter (for example requiring an extra letter then a digit) does not permit arbitrary repetition of letters or digits and therefore does not match the Kleene-star part of the regex.
Concise construction to keep in mind:
Start state --(letter)--> accepting state.
Accepting state --(letter or digit)--> accepting state (loop).