Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

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

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a 

What is L(G1)?

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

(c) Is L₂ inherently ambiguous?

A simple Pascal like language has only three statements.
(i) assignment statement e.g. x:=expression
(ii) loop construct e.g. for i:=expression to expression do statement.
(iii) sequencing e.g. begin statement ;…; statement end

(a) Write a context-free grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional parentheses and * operator in CFG.
(b) Show the parse tree for the following statement:

     for j:=2 to 10 do
         begin x:=expr1;
               y:=expr2
         end