Computer Sciences > GATE 2025 SET-1 > Finite Automata
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.
A
The set of all strings containing an even number of b's.
B
The set of all strings containing the pattern bab.
C
The set of all strings ending with the pattern bab.
D
The set of all strings not containing the pattern aba.

Correct : c

Labelling the states left to right as q0 (start), q1, q2, q3 (accepting), the transitions from the image are:
q0: a→q0, b→q1
q1: b→q1, a→q2
q2: a→q0, b→q3
q3: a→q2, b→q1
Option A — False
"bb" has 2 b''s (even) but traces q0→q1→q1, ending in q1 which is not accepting. DFA does not accept all strings with even number of b''s.
Option B — False
"babb" contains "bab" but traces q0→q1→q2→q3→q1, ending in q1 which is not accepting. DFA does not accept all strings containing "bab".
Option C — True
The DFA precisely tracks whether the last three characters form "bab". State q1 means the suffix so far ends in b, q2 means it ends in ba, q3 means it ends in bab (accepting). The DFA resets appropriately on mismatches. All strings ending with "bab" are accepted and nothing else is — the accepting state q3 is only reached when the last three characters read were exactly b, a, b.
Option D — False
"b" does not contain "aba" but traces q0→q1, not accepting. The DFA rejects "b" so it cannot be accepting all strings not containing "aba".
Correct answer: C

Similar Questions

Which one of the following regular expressions correctly represents the language of the finite automaton given below?
#783 MCQ
A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?
#1371 MCQ
Let Σ={1,2,3,4}. For x∈Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ε)=1, where ε is the null string.F...
#1467 NAT

Related Topics

DFA language accepted bab GATE 2025 GATE CS 2025 Set-1 Q50 finite automaton strings ending bab GATE DFA 4 states alphabet ab GATE CS theory of computation DFA language GATE 2025 strings ending bab DFA pattern matching GATE

Unique Visitor Count

Total Unique Visitors

Loading......