Consider the following grammar :
S → 0A ∣ 0BB
A → 00A ∣ λ
B → 1B ∣ 11C
C → B Which language does this grammar generate?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. L((00)*0)
Explanation
B → 1B | 11C and C → B never produce a terminal-only string, so B is useless and S → 0BB is dead. What remains is S → 0A with A → 00A | λ: (00)*0.
More Theory of Computation and Compilers questions
- Let Σ = {w, x} and T = {x, y, z}, with homomorphism h(x) = xzy and h(w) = zxyy. If L is denoted by r = (w + x*)(ww)*, then h(L) is denoted…
- Consider the following statements with respect L = {anbn ∣ n ≥ 0} to the language S : L2 1 is context free language S : Lk 2 is conext-free…
- Consider the following languages : L = {anbncm} ∪ {anbmcm}, n, m ≥ 0 1 L = {wwR ∣ w ∈ {a, b}*} 2 Where R represents reversible operation. W…
- Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on th…
- Consider the following language families : L ≡ The context - free languages 1 L ≡ The context - sensitive languages 2 L 3 ≡ The recursively…
- Consider the following statements : S 1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same lan…