IAE Academy

ISRO CS 2023 Q.7: solution and answer

ISRO 2023 · CSQ.7 · 1 mark · MCQ

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-z A-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?

ISRO CS 2023 question 7: An NFA with epsilon-transitions.Tap to open full size
Figure from the ISRO CS 2023 paper. It is part of the question.
Figure description

An NFA with epsilon-transitions. A start state (small incoming arrow from the left) has an edge labelled 'letter' to a double-circled final state F. From F, two epsilon edges leave: the upper one goes to a state from which an edge labelled 'letter' leads to another state, and the lower one goes to a state from which an edge labelled 'digit' leads to another state. Each of these two end states has an epsilon edge into a common join state at the right. From the join state a long epsilon edge, drawn as an arc over the top, returns to F.

  1. (A)

    letter (letter | digit)*

  2. (B)

    (letter | digit)* letter

  3. (C)

    (letter | digit)*

  4. (D)

    letter (letter* | digit*)

Answer and solution

ANSWER

The NFA accepts exactly the strings described by , which is option (A).

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

  1. The start state has one edge, labelled letter, into the double-circled state . Every accepted string therefore begins with exactly one letter.

  2. From , one -edge leads to a state with a letter edge. A second -edge leads to a state with a digit edge. These are the two branches of an alternation, letter | digit.

  3. Both branches end in -edges that meet at a common join state. This is the standard union construction.

  4. The join state has an -edge back to , so the alternation can be repeated any number of times. is the only final state, and the loop passes through it. Zero repetitions are accepted, because the machine can stop at right after the first letter. This loop is the Kleene star (letter | digit)*.

  5. The accepted language is one letter followed by zero or more symbols, each a letter or a digit: letter (letter | digit)*. This is option (a).

  6. Option (b) requires the string to end in a letter. The NFA also accepts strings that end in a digit, such as a1, so (b) is wrong.

  7. Option (c) accepts the empty string and strings that start with a digit. The NFA accepts neither, because it needs an initial letter. So (c) is wrong.

  8. Option (d) lets the tail be only letters or only digits. It cannot produce a1b, which the NFA accepts by taking the digit branch and then the letter branch. So (d) is wrong.

KEY IDEA

Read an NFA as a regular expression piece by piece. An alternation is two parallel branches joined by -edges. An -edge from the join back to an earlier final state is a Kleene star. The edge before that state is a prefix that appears only once.

WATCH OUT FOR

Overlooking the initial letter edge before the loop and choosing (letter | digit)*. That option also accepts the empty string and strings starting with a digit, which an identifier cannot be.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 3 ISRO Lexical analysis questions, with notes