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.
For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 
Explanation
A is an NFA (state 1 has two moves on a). B is missing the move from state 3 on a, so it rejects strings like ababb. C defines a move for every state and symbol and accepts exactly the strings containing abb (states 4, 5, 6 are all accepting), so it is a valid, though not minimal, DFA.
More Theory of Computation and Compilers questions
- 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…
- Which of the following is a context-free language? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l} (C) {…