Directions (Q91–95): A machine is represented by states Q, input alphabet Σ, transition function δ, initial state q0 and final states F. The machine accepts all strings over Σ = {a, b} which start and end with any combination of the alphabet symbols, and in which abb occurs as a substring (i.e. the language of all strings over {a, b} containing abb).
Which of the following represents 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: D. All are NFA
Explanation
Options A and B both have two transitions on the same symbol from one state (e.g. 2 –a→ 2 and 2 –a→ 3), and option C has missing transitions (state 1 on b, state 5 on a) and is not minimal. None of them is a (minimal) DFA. The minimal DFA has 4 states: q0 (b→q0, a→q1), q1 (a→q1, b→q2), q2 (a→q1, b→q3), q3 final (a, b → q3).More Theory of Computation and Compilers questions
- For the above specified passage, which of the following is a DFA for the language accepted by the machine?
- For the above specified passage, which of the following represents the regular expression?
- Consider the grammar: S → A A → $B$ | id B → B, A | A If I₀ = CLOSURE({[S → ·A]}), then how many items will be in the set GOTO(I₀, $)?
- 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 FOLLO…
- Which of the following properties correctly describe a Regular Grammar? (A) All production rules are of the form A → xB or A → x, where A a…
- If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?