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

The set of all strings ending with the pattern bab.

The set of all strings containing an even number of b's.

The set of all strings containing the pattern bab.

The set of all strings ending with the pattern bab.

The set of all strings not containing the pattern aba.

GATE CSE 2025 Session 1 Q50: Language accepted by a four-state DFA

Theory of Computation
2 marks
MSQ
No negative marking

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.

DFA with four states in a row, q0 (start), q1, q2 and q3 (accepting). q0: a loops, b to q1. q1: b loops, a to q2. q2: b to q3, a back to q0. q3: a to q2, b to q1. — Tap the figure to enlarge

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: C (official GATE 2025 final answer key)

Concept used: Each DFA state remembers the longest suffix that is a prefix of a target pattern.

First step: Label states by the suffix read so far: start = none, after b = "b", after ba = "ba", accepting = "bab"; then check what a and b do from the accepting state.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2025 Session 1 questions →

GATE CSE 2025 Session 1 Q50: Language accepted by a four-state DFA

Question

Full step-by-step solution

More Theory of Computation PYQs