(a) Let G1 = (N, T, P, S1) be a CFG where N = {S1, A, B}, T = {a, b}, and P is…

PYQ GATE 1998

(a) Let G1 = (N, T, P, S1) be a CFG where N = {S1, A, B}, T = {a, b}, and P is given by

S₁ → aS₁b  |  aAb  |  aBb
A  → aA    |  a
B  → Bb    |  b

What is L(G1)?

(b) Use the grammar in part (a) to give a CFG for L2 = {aibjakbl | i, j, k, l ≥ 1, i = j or k = l} by adding not more than 5 production rules.

(c) Is L2 inherently ambiguous?

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…