Self_Doubt

Question

NPDA which accepts by final state there is an equivalent NPDA (equivalent means that accepts the same language) which accepts by empty stack and vice-verse. I agree with this point .

But plz anyone show me one simple  NPDA which accepts regular language using empty stack mechanism.

Answer 1

Say ww^r is NPDA. Why is it NPDA? Because we donot know the midpoint of the NPDA. So, here push and pop will be random access. Like say ababccbaba

Now, firstly it will try to take a in push , babccbaba as pop. But not accepted. So, discard it.

Next ab to push  and then abccbaba as pop. will not accept, So discard it...........So, on

When it get ababc as push and cbaba as pop , it will get accepted.

So, get empty stack here. No need of furthur computation

Comments

@srestha

But my question is "plz anyone show me one simple  NPDA which accepts regular language using empty stack mechanism"

WW^r is not regular language it is CFL.

Can u plz show me a* (RL) using NPDA by empty stack mechanism or any other RL.

---

But Regular language is already deterministic. So, why u want to imlement it in stack?

---

@srestha we can't draw DPDA for Regular language using empty stack mechanism but we can draw NPDA for Same .

So I want to draw NPDA which realize regular language using empty stack mechanism.