The GATE Grind

GATE 2025 CS (CS1) – Question 50

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple select

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a,b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

Diagram for GATE 2025 CS (CS1) question 50
  1. The set of all strings containing an even number of $b$'s.
  2. The set of all strings containing the pattern $bab$.
  3. The set of all strings ending with the pattern $bab$.
  4. The set of all strings not containing the pattern $aba$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) The set of all strings ending with the pattern $bab$.

Explanation

State meanings (longest suffix read so far that is a prefix of `bab`): $q_0$: none, $q_1$: `b`, $q_2$: `ba`, $q_3$: `bab`.

Check each transition against that meaning:
- $q_0\xrightarrow{a}q_0$, $q_0\xrightarrow{b}q_1$.
- $q_1\xrightarrow{b}q_1$ (suffix `bb` still ends in `b`), $q_1\xrightarrow{a}q_2$.
- $q_2\xrightarrow{b}q_3$ (we just completed `bab`), $q_2\xrightarrow{a}q_0$ (`baa`: no useful suffix).
- $q_3\xrightarrow{a}q_2$ (`baba`: suffix `ba`), $q_3\xrightarrow{b}q_1$ (`babb`: suffix `b`).

Since $q_3$ is accepting and has outgoing transitions (it is not absorbing), the DFA accepts exactly the strings that **end** in `bab`: option (C). (It does not accept all strings that merely contain `bab`.)

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →