The reduced grammar equivalent to the grammar whose production rules are given below is
S → AB | CA
B → BC | AB
A → a
C → aB | b
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. S → CA, A → a, C → b
Explanation
B can never derive a terminal string (every B-production contains B), so B is useless. Removing it leaves S → CA, A → a, C → b.More Theory of Computation and Compilers questions
- Consider the production rules of grammar G: S → AbB A → aAb | λ B → bB | λ Which language L is generated by G?
- Consider the language L = {anbm : n ≥ 4, m ≤ 3}. Which regular expression represents L?
- Consider L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- Consider the NPDA M = ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)} δ(q0, a, z) = {(q1, 11z)} δ(q1, a, 1) = {…
- Consider two instances X and Y of the Post Correspondence Problem, each with lists A and B of three strings over {0, 1}. Which of the follo…
- Consider the following properties of recursively enumerable sets: (A) Finiteness (B) Context-freedom (C) Emptiness Which of the following i…