Question
Official answer and solution
- Official answer
- C
- From
- Official GATE 2023 answer key
Solution
Trace the transitions from start state to accepting state and find the regular expression.
- From start state :
- Reading transitions to state , which is a dead (trap) state with self-loops on .
- Reading transitions to state , which is the only final (accepting) state.
- From accepting state :
- Reading stays in (self-loop).
- Reading transitions to state .
- From state :
- Reading transitions to dead state .
- Reading transitions back to state .
- Therefore, every accepted string must start with (to reach ). Once at , any sequence composed of single 's (staying at ) or blocks of () returns to . Any other symbol sequence leads irreversibly to dead state .
Thus, the language accepted is .
Final answer
Option (C)
Common trap
Thinking must precede or can only occur inside , whereas and 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.