0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Is there some reason to disallow the start state being an accepting state? $\endgroup$ – Luke Mathieson Nov 12 '14 at 23:35
  • $\begingroup$ Wow, hadn't even considered that. Thank you very much! $\endgroup$ – Connal Sumlin Nov 12 '14 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$ – Hendrik Jan Nov 13 '14 at 0:04
  • $\begingroup$ @LukeMathieson Make an answer? $\endgroup$ – Raphael Nov 13 '14 at 7:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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