GATE 2023 CS Q.19: solution and answer

GATE 2023 · CSQ.19 · 1 mark · MCQ

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)

GATE 2023 CS question 19: Four NFAs with ε-transitions, each starting from a start state (arrow in). — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
Figure — NFA (A) as described
(B)
Figure — NFA (B) as described
(C)
Figure — NFA (C) as described
(D)
Figure — NFA (D) as described

Answer and solution

ANSWER

The NFA in option (C) accepts exactly the valid identifiers, so the answer is (C).

Official answer: CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

The target language is $L = letter (letter ∣ digit)^{*}$ : one letter first, then any mix of letters and digits, in any order, of any length (including none).
(A): the start state $q_{0}$ has an $ε$ -move to the final state $q_{1}$ , so the empty string $ε$ is accepted. Since $ε \in / L$ , (A) is wrong.
(B): after the first letter, the machine takes an $ε$ -move to one of two separate final states. One loops only on letter, the other only on digit, so it accepts $letter letter^{*}$ or $letter digit^{*}$ but never a mix. The string letter digit letter is rejected although it is in $L$ , so (B) is wrong.
(D): after the first letter the machine reaches the final state $q_{1}$ , and from there it can only read letter then digit before an $ε$ -move returns it to $q_{1}$ . It accepts $letter (letter digit)^{*}$ . The string letter digit, which is in $L$ , is rejected, so (D) is wrong.
(C): the first letter leads to the final state $q_{1}$ . From $q_{1}$ two $ε$ -branches start, one reading letter and one reading digit. Both end in a non-final state that has an $ε$ -move back to $q_{1}$ .
So each trip around the loop through $q_{1}$ reads exactly one letter or one digit, in any order and any number of times, and $q_{1}$ is final. This is the standard construction for $(letter ∣ digit)^{*}$ placed after the first letter, so the machine accepts exactly $L$ .
Hence the answer is (C).

KEY IDEA

A letter, then a loop of choices (letter | digit) that returns to a final state, is how $letter (letter ∣ digit)^{*}$ is built. Check each option for $ε$ , for a mixed string like letter digit letter, and for a single letter followed by a digit.

WATCH OUT FOR

Choosing (B) because it has both a letter loop and a digit loop. The two loops sit on separate final states, so a letter and a digit can never be mixed after the first letter.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2023 CS Q.19: solution and answer

Answer and solution

More Finite automata questions