3
$\begingroup$

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example of regular language a*. Here if we use stack then we can't decide when to pop the symbols from stack. If we pop all the symbols(prefix belonging to language) then stack will become empty and we can't process the input further(left over input). So we can't accept a* using dpda by stack.

I read another statement that NPDA using stack can accept all languages which NPDA using final state will accept. Here we can have many copies of machine running simultaneously and we can non deterministically check if the input is accepted or not. But what if prefix like aa of input aaaaa is accepted by one of the machine ? Will all the machines stop and say yes (that is we can't proceed with the input further) or will some of the machines still continue with the remaining input even if one of them halts?

$\endgroup$
  • $\begingroup$ "Here we can have many copies of machine running simultaneously" -- that's not a useful intuition. Stick with the definition! $\endgroup$ – Raphael Oct 8 '17 at 20:23
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 8 '17 at 20:24
  • $\begingroup$ Your question is not answerable. First, your title does not suite the body of your post, please improve it. Second, according to your questions you seem to confuse how a PDA/NPDA works and it has nothing to do with the "prefix property". If you do not understand how PDA/NPDA/DPDA operates, you can ask a specific question which part of the definition you do not understand. We already have a similar question here. $\endgroup$ – fade2black Oct 8 '17 at 22:09
  • $\begingroup$ @fade2black I read your answer. You said "Each branch may accept or reject input. If at least one branch halts with accept then the NPDA accepts that input. Otherwise it rejects." . Now what if that one branch is the one which accepts the prefix of the language before other branches ? What happens to other branches? $\endgroup$ – Zephyr Oct 8 '17 at 22:17
3
$\begingroup$

A nondeterministic PDA for any triple $\langle q,a,A\rangle$ may have more than one moves/transitions and so the NPDA may have different computation paths/branches depending on what choice the NPDA makes (see this definition for details). So, for any input $x$ if at least one of these sequence of choices leads to an accepting configuration then we say the NDPA accepts $x$. In this case whether or not other possible computation branches lead to an accepting configuration does not matter. At least one accepting path is enough to accept the input $x$.

Now, regarding the question in your comment:

Now what if that one branch is the one which accepts the prefix of the language ? What happens to other branches?

You presumably mean "the prefix of a string", in particular, say $x=aaaaa$ and its prefix $y=aa$. For a NPDA $x$ and $y$ are two different inputs, the NPDA may accept or reject both strings or accept only one of them. This absolutely has nothing to do with the prefix property of a language.


Example: a PDA accepting the set of odd length $a$s and and empty string. The basic idea is to keep track of how many $a$s are read, even or odd number of $a$s, using the stack symbols.

$\delta(q,a, Z_0) = (q,Z_{odd})$
$\delta(q,a, Z_{odd}) = (q,Z_{even})$
$\delta(q,a, Z_{even}) = (q,Z_{odd})$
$\delta(q,\epsilon, Z_{odd}) = (q_1,\epsilon)$
$\delta(q_1,\epsilon, Z_0) = (q_1,\epsilon)$
$\delta(q_1,\epsilon, Z_{even}) = (q_1,\epsilon)$
$\delta(q_1,\epsilon, Z_{odd}) = (q_1,\epsilon)$

This PDA is not deterministic due to the following two transitions:

$\delta(q,a, Z_{odd}) = (q,Z_{even})$
$\delta(q,\epsilon, Z_{odd}) = (q_1,\epsilon)$

In other words it has two choices when it is in the state $q$ and the topmost stack symbol is $Z_{odd}$.

Now suppose this PDA reads $aaaaa$. After reading the third $a$ it may enter the state $\delta(q,\epsilon, Z_{odd}) = (q_1,\epsilon)$ which will empty the stack but the rest of the input are not read, and so this branch does not accept the input. However, the PDA has another choice, namely $\delta(q,a, Z_{odd}) = (q,Z_{even})$ which leads to accepting the $aaaaa$.

$\endgroup$
  • $\begingroup$ Actually the main problem which I am not able to understand is how is NPDA using empty stack equivalent to NPDA using final state. For DPDA I understood that stack one is subset of final state one and the languages accepted by them are not same. $\endgroup$ – Zephyr Oct 8 '17 at 23:08
  • $\begingroup$ That is another question. Reference: "Introduction to Automata Theory, Languages, and Computation" by J. Hopcroft and J. Ullman's, pg. 114, Theorem 5.1: Equivalence of acceptance by final state and empty stack. $\endgroup$ – fade2black Oct 8 '17 at 23:14
  • $\begingroup$ You said "for any input x if one the branches leads to accepting sequence then NPDA accepts it". Now if I give input aaaaa and suppose one branch accepts aaa, the stack becomes empty for that branch and NPDA would think that input was aaa and accept it without processing remaining 2 a's. So, stack of one branch doesn't affect other branches ? $\endgroup$ – Zephyr Oct 9 '17 at 6:08
  • $\begingroup$ @Zephyr please do not mix NPDA with DPDA. In fact I can design a NPDA with two states accepting the set of odd $a$s by empty stack, but there is no DPDA accepting that language by empty stack. Unlike NFA and DFA, NPDA and DPDA are not equal regarding their computability powers. $\endgroup$ – fade2black Oct 9 '17 at 6:14
  • 1
    $\begingroup$ I updated my post. Please see the example of PDA/NPDA. The last three instructions empty the stack. $\endgroup$ – fade2black Oct 9 '17 at 6:50

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.