Explain the difference between Regular Grammar and Context-Free Gramma Remove th

Question

Explain the difference between Regular Grammar and Context-Free Gramma Remove the productions with forms A rightarrow lambda and A rightarrow B from the following grammar equivalent grammar ( first remove D rightarrow C; then remove C rightarrow lambda). S rightarrow aD | aaC | CaCD C rightarrow b | Db D rightarrow C C rightarrow lambda Consider the grammar G = (V, T, E, P) with V = {E, I}, T = {x, y, z, -x (,)}, and productions E rightarrow i, E rightarrow E - E, E rightarrow E times E, E rightarrow (E), I = x |y|z. (i) Show that G is ambiguous by giving two different derivation trees for string b times c - a (ii) Change the above grammar into the one without ambiguity. (i) What language is accepted by the Turing machine M = ({q_0, q_1, q_2}, {a, b}, {a, b,}, delta, q_0, {q_3}) with delta (q_0, a) = (q_1, b, R), delta (q_1, a) = (q_1, v, R), delta (q_1, b) = (q_1, a, R), delta (q_1, ) = (q_2,, L) delta (q_2, a) = (q_3, a, R) (ii) What language is accepted by the Turing machine M = ({q_0, q_1, q_2, q_3}, {a, b}, {a, b,}, delta q_0, {q_2}) with

Explanation / Answer

Answer to question 3 is as follows:

D->C and C->lemda

HenceD->lemda

So we can replace the following in the grammer

S->a |aaC |CaC
C ->b

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.