0
$\begingroup$

Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just continue moving after reading w when the stack is empty until we read the whole input and decide whether we accept the word by looking at the stack state?

$\endgroup$
1
$\begingroup$

A transition in a PDA always needs to read a symbol in the stack. If there is no symbol, there is no transition.

Since the PDA is deterministic, reading $w$ will always reach a configuration with an empty stack, and no transition can permit to read any non empty word.

$\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.