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).
For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. States 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4
Explanation
Option A accepts strings ending with abb and option B accepts strings starting with abb. Option C loops on any symbols before abb (state 1) and after it (state 4), so it accepts exactly the strings containing abb. Option D also accepts ε and strings without abb.More Theory of Computation and Compilers questions
- For the above specified passage, which of the following represents the grammar for the language accepted by the machine?
- Which of the following represents the minimum-state DFA for the above specified passage?
- 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…