Directions (Q91–95): A machine is represented by states Q, input alphabet Σ = {a, b}, a transition function δ, initial state q0 and final states F. It accepts all strings over Σ that contain abb as a substring, with any combination of a and b before and after it.
Which of the following represented the minimum state DFA for the above specified passage?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 
Explanation
The minimal DFA for strings containing abb needs 4 states tracking the longest matched prefix: 1 (loop on b, a → 2), 2 (loop on a, b → 3), 3 (a → 2, b → 4), 4 accepting with a loop on a, b. Figure B is exactly this complete DFA, so B is the answer.
Note on the official key: the official key says option D. PW/official key gives D (All are NFA); figure B is a complete minimal DFA.
More Theory of Computation and Compilers questions
- For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
- For the above specified passage, which of the following represents the regular expression?
- Consider the Grammar: T → Qx Q → RS R → y ∣ ϵ S → z ∣ ϵ Here x, y, z are terminals and T, Q, R, S are non- terminals. What will be the foll…
- Which of the following tasks could be attained using syntax trees in compiler design ? (A) Type Checking (B) Code Generation (C) Code Optim…
- Arrange the following stages of parsing in the correct order as they typically occur in the compilation process. (A) Lexical Analysis (B) S…
- Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy: (A) Context…