• Input: CFG G =
(N, T, P, S)
• Output: EPDA M = (Q, S, G, R, s, #, F);
L(G) = L(M)f
• Method:
• Q
:= {s, f};
• S := T;
• G := N
È T È {#};
• Construction of R:
• for every a Î S, add sa ® as to R;
• for every A ® x Î P, add xs ® As to R;
• add #Ss ® f to R;
• F :=
{f};