A machine is represented by states Q, input alphabet Σ, transition function δ,…
2025
A machine is represented by states Q, input alphabet Σ, transition function δ, initial state q₀ and final state F. The machine accepts all the strings over Σ = {a, b}, which start and ended with any combination of all alphabet and abb works/lies as substring in all the strings to be accepted.
For the above mentioned passage which of the following is correct?
Attempted by 128 students.
Show answer & explanation
Correct DFA and explanation for the language: all strings over Σ = {a, b} that contain the substring "abb".
Key idea: build states that record how much of the target substring "abb" has been seen so far, and make a sink accepting state once the full substring is seen.
States:
q0 (start): no part of "abb" seen yet.
q1: an initial 'a' has been seen (possible start of "abb").
q2: 'ab' has been seen (we are one more 'b' away).
q3 (accepting): 'abb' has been seen; remain here for all further input.
Transitions:
From q0: on 'a' → q1; on 'b' → q0.
From q1: on 'a' → q1 (an 'a' could start a new match); on 'b' → q2.
From q2: on 'a' → q1 (the 'a' could begin a new attempt); on 'b' → q3 (we have seen 'abb').
From q3: on 'a' → q3; on 'b' → q3 (once accepted, stay in accepting state).
Why this works:
The states track longest suffix of the input that matches a prefix of "abb". When the machine reaches q3 it has just read "abb" and will accept any continuation.
Overlapping occurrences are handled because transitions from q2 on 'a' go to q1, which allows the machine to start matching a new "abb" immediately.
A video solution is available for this question — log in and enroll to watch it.