Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.