• Input: CFG G =
(N, T, P, S)
• Output: PDA M = (Q, S, G, R, s, S, F); L(G) = L(M)e
• Method:
• Q
:= {s};
• S := T;
• G := N
È T;
• Construction of R:
• for every a Î S, add asa ® s to R;
• for every A ® x Î P, add As ® ys to R,
where y = reversal(x);
• F :=
Æ;