We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong
But can we have a non empty stack at the start? is my method right?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
But can we have a non empty stack at the start?
By the formal definition PDA has the initial stack symbol $Z$ with which a computation starts.
The idea is to use three stack symbols $Z, Z_{even}, Z_{odd}$ to keep track of whether the number of $a$s read so far is even or odd. If the PDA reaches the end of string and topmost symbol is $Z_{odd}$ then empty the stack.
answered Sep 26, 2017 at 15:39
-
$\begingroup$ Thanks for the answer, so therefore we can have a DPDA which accepts this language with one state for this right? $\endgroup$ Commented Sep 26, 2017 at 15:43
-
$\begingroup$ @fade2black, I read that acceptance of DCFL by empty stack is possible only if prefix property is not satisfied. Here if we have a string aaaaa, then prefix of this string(aaa) also belongs to the language so we can't decide when to pop and if we pop all three a's, then we can't read the input further as stack becomes empty and string is accepted. Is that prefix property only valid for DPDA with only one stack symbol ? $\endgroup$– ZephyrCommented Oct 8, 2017 at 17:51
-
$\begingroup$ @EdaiBossinShid Sorry for the late reply (just seen after Zephyr's comment). I think better late than never. If we try to design a DPDA with a single state then it must accept by empty stack. But this language does not have the prefix property (see this post) so it is impossible to come up with a DPDA accepting by empty stack. My hint which suggests a PDA with three stack symbols is in not a DPDA. $\endgroup$ Commented Oct 8, 2017 at 21:04
-
$\begingroup$ @Zephyr it does not matter how many stack symbols you use. If a language does not have the prefix property then it cannot be accepted by a DPDA with empty stack (see also this post). $\endgroup$ Commented Oct 8, 2017 at 21:07
-
$\begingroup$ @fade2black Under your answer, there is a comment which says L={b^n ,n>=0} is accepted by DPDA if we have more stack symbols and states. So it means DPDA can have more than one stack symbols. Is it correct? $\endgroup$– ZephyrCommented Oct 8, 2017 at 21:26