Self Doubt

Question

For Language $L=\{a^{n}b^{n}|n\geq 0\}$

Design Final state PDA and Empty Stack PDA$?$

I can able to design Final state PDA, can someone explain in detail to design Empty Stack PDA$?$

I have another doubt acceptance of  Final state PDA and Empty Stack PDA are the same in case of NPDA, but in case of DPDA I don’t know$?$

 

Comments

I got this theorem

Theorem: A language L is accepted by a DPDA by empty stock if and only if it has the prefix property and is accepted by some DPDA by final state. 

So, I think prefix property could be a reason

right?

 

 

---

@Shaik Masthan

@ankitgupta.1729

please have a look at it

---

Some basic point here

 After empting a stack there is no transition possible for that grammar. So, after that we cannot get a final state transition

But after final state and after accepting language, if we empty the stack, that is possible  So, final state transition possible for empty state transition

So, final state transition is more powerful than empty stack transition in DPDA

Answer 1

PDA is of two types i) DPDA ii) NPDA

• DPDA with Final state is more powerful then DPDA with the empty stack.

Example${\color{Magenta} {:L=\{a^nb^nc^m|n,m\geq0\}}}$ it is deterministic context-free language (DCFL) we can make a DPDA with final state.  but we can not make a DPDA with the empty stack for this language. so we can say DPDA with Final state is more powerful.

• NPDA with Final state and  NPDA with empty stack,both have the same power. 

 

Comments

@abhishekmehta4u

@Lakshman Patel RJIT

does it mean empty state PDA doesnot accept anything, as it has no final state?