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 represents the grammar for the language accepted by the machine?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. S → AabbA, A → aA | bA | ε
Explanation
A → aA | bA | ε generates (a + b)*, so S → A abb A generates (a + b)* abb (a + b)*. Option A only allows a* before and b* after, B forces the string to start with abb, and D forces it to end with abb.More Theory of Computation and Compilers questions
- 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…
- 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…