Question

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0,1}\{0, 1\}, and has the set of states {s,p,q,r}\{s, p, q, r\}, with ss being the start state and pp being the only final state.

DFA A with states {s, p, q, r}, start state s, final state p, transitions s->p on 1, s->r on 0, p->p on 0, p->q on 1, q->p on 1, q->r on 0, and r->r on 0,1.

Which one of the following regular expressions correctly describes the language accepted by A?

Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2023 answer key

Solution

Trace the transitions from start state ss to accepting state pp and find the regular expression.

  1. From start state ss:
    • Reading 00 transitions to state rr, which is a dead (trap) state with self-loops on 0,10, 1.
    • Reading 11 transitions to state pp, which is the only final (accepting) state.
  2. From accepting state pp:
    • Reading 00 stays in pp (self-loop).
    • Reading 11 transitions to state qq.
  3. From state qq:
    • Reading 00 transitions to dead state rr.
    • Reading 11 transitions back to state pp.
  4. Therefore, every accepted string must start with 11 (to reach pp). Once at pp, any sequence composed of single 00's (staying at pp) or blocks of 1111 (p→1q→1pp \xrightarrow{1} q \xrightarrow{1} p) returns to pp. Any other symbol sequence leads irreversibly to dead state rr.

Thus, the language accepted is 1(0+11)∗1(0 + 11)^* .

Final answer

Option (C)

Common trap

Thinking 00 must precede 1111 or can only occur inside (0∗11)∗(0^* 11)^*, whereas 00 and 1111 can be interleaved arbitrarily.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2023 Computer Science and Information Technology (CS)
Question
14 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.