Can a DPDA be created for a Language which includes the null string?

The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a state, a is some input, and Z is a stack-character.

Also, if you have a transition Delta(q,lambda,Z), you can't accept any other input from that state.

So, back to the original question. Can a DPDA accept a language which lambda and anything else?

  • 1
    $\begingroup$ Is there some reason to disallow the start state being an accepting state? $\endgroup$ Nov 12, 2014 at 23:35
  • $\begingroup$ Wow, hadn't even considered that. Thank you very much! $\endgroup$ Nov 12, 2014 at 23:45
  • $\begingroup$ To be precise, that depends on the mode of acceptance. When using final-state acceptance see Luke's comment. We can also consider empty stack acceptance, which is useful when proving the equivalence between PDA and CFG. For nondeterministic automata the two modes are equivalent. In the deterministic case and empty-stack the languages are prefix-free: when a string is accepted, no proper extensions belong to the language. Perhaps this confusion led to your question? $\endgroup$ Nov 13, 2014 at 0:04
  • $\begingroup$ @LukeMathieson Make an answer? $\endgroup$
    – Raphael
    Nov 13, 2014 at 7:08

1 Answer 1


Yes, we can simply make the starting state an accept state. With no input (i.e. empty string) the machine halts immediately, and accepts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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