0
$\begingroup$

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$ ?

  • 0
    @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 free2012-10-06

1 Answers 1

1

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.

  • 0
    @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.2012-10-07