GATEverse — GATE CSE previous year questions

(A)

Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ is given by

\begin{array}{l|l} S_1 \rightarrow a S_1 b &S_1 \rightarrow a B b \\ S_1 \rightarrow a A b & B \rightarrow Bb\\ A \rightarrow a A & B \rightarrow b\\ A \rightarrow a \end{array}

What is $L(G_1)$ ?

(B)

Use the grammar in Part(a) to give a CFG for $L_2 = \{a^ib^ja^kb^l \mid i, j, k, l \geq 1, i=j \text{ or } k=l\}$ by adding not more than $5$ production rules.

(C)

Is $L_2$ inherently ambiguous?