Consider a DFA defined over the alphabet Σ = {a, b}. Identify which of the following language(s) is/

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Theory of Computation paper.

Q: How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Finite Automata (DFA and NFA) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2025 Theory of Computation question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider a DFA defined over the alphabet Σ = {a, b}. Identify which of the following language(s) is/are accepted by the given DFA.

Accepted Answer

Correct Answer: (C) The set of all strings ending with the pattern bab.Concept — DFA for Suffix Pattern Recognition: A DFA that recognizes strings ending with a fixed pattern P tracks the longest suffix of the input processed so far that is also a prefix of P. When the full pattern P has been matched as a suffix, the DFA is in an accepting state.For the pattern "bab" over {a, b}: The DFA has states corresponding to how many characters of "bab" have been matched as the current suffix:q₀: No prefix of "bab" is a suffix of the current input (start state).q₁: The current suffix matches "b" (first character of "bab").q₂: The current suffix matches "ba" (first two characters).q₃: The current suffix matches "bab" (full pattern) → accepting state.The DFA accepts a string if and only if it ends with "bab". From the given DFA figure, this is the language described in Option C.Why other options are wrong:Option A (even number of b's): Requires a 2-state DFA toggling on each 'b', not a 4-state pattern-matching DFA.Option B (contains bab anywhere): The DFA for "bab anywhere" would not require the suffix to be "bab" — once accepted, any additional input would still keep the string accepted. This DFA doesn't behave that way.Option D (not containing aba): This is the complement of a different pattern recognition — not what this DFA computes.

Consider a DFA defined over the alphabet Σ = {a, b}. Identify which of the following language(s) is/are accepted by the given DFA.

Master GATE-CS with Our Test Series

More Questions from Finite Automata (DFA and NFA)

Frequently Asked Questions

Consider a DFA defined over the alphabet Σ = {a, b}. Identify which of the following language(s) is/are accepted by the given DFA.

Master GATE-CS with Our Test Series

More Questions from Finite Automata (DFA and NFA)

Frequently Asked Questions