• 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 := Æ;
Algorithm: From CFG to PDA
47/50