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 specified passage, which of the following is a DFA for the language accepted by the machine?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. States 1–6, final {4, 5, 6}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –b→ 4, 4 –a→ 5, 5 –a→ 5, 5 –b→ 6, 6 –a→ 5, 6 –b→ 4
Explanation
Option A is an NFA (1 has two a-moves). Option B has no a-move from state 3, so it wrongly rejects strings like 'abaabb'. Option D tracks 'bb…' patterns from the start state and accepts strings without abb. Option C is complete and deterministic: states 1–3 track progress towards abb and states 4–6 (all final) are reached only after abb has occurred, so it accepts exactly the required language (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: 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₂?
- Which of the following tasks could be attained using syntax trees in compiler design? (A) Type Checking (B) Code Generation (C) Code Optimi…