# Proving that for every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$

The book I am reading have proof for the statement

Every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$

For the case $\epsilon\not\in L$. The proof uses greibach normal form (hence the reason for the condition $\epsilon\not\in L$)

How can I prove this statement (preferably not having to re-prove everything again) for the general case ?

I understand that we can add the single rule $S\to\epsilon$ to the grammar after it's in greibach normal form, but how can I make the pushdown automata also accept $\epsilon$ ?

-
Does $\epsilon \in L$ simply mean that the empty (zero-length) word is not in the language $L$? Or do you mean something more complex by that, like $L$ having a context-free gramming with doesn't include rules of the form $A \rightarrow \epsilon$? If it's the former, what's the problem with constructing the automatom for $L \setminus \epsilon$, and then modifying it to also accept $\epsilon$? – fgp Oct 6 '12 at 22:09
@fgp - the statement has been proved for the case that the empty (zero-length) word is not in the language and I am asking of a proof for the general case - i.e. without demanding anything of $L$ beside being context free – Belgi Oct 6 '12 at 22:11

I’m assuming that $L_e$ means that you’re accepting by empty stack. In that case you should be able simply to modify $\delta(q_0,\epsilon,Z)$, where $Z$ is the initial stack symbol, by adding $(q_0,\epsilon)$. That is, if $\delta(q_0,\epsilon,Z)=A$ in the original PDA, let $\delta(q_0,\epsilon,Z)=A\cup\{(q_0,\epsilon)\}$ in the modified PDA.
Does this modification to a PDA changes it langauge so it will additionally accept $\epsilon$, but won't add any other words or remove words from the language ? I think so, but I want to be sure. thanks for the help! – Belgi Oct 7 '12 at 10:47
@Belgi: It can’t remove anything. It can’t add anything besides $\epsilon$ unless the existing PDA can return to $q_0$ with just $Z$ on the stack. If I remember Greibach normal form correctly, that shouldn’t happen, but in any case it’s the only potential problem. – Brian M. Scott Oct 7 '12 at 10:51