self doubt

Question

Consider the Context free language  which has equal no of as and bs. 

eg- abab

Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. 

But we can clearly draw a deterministic PDA with empty stack acceptance for it.

My doubt is that we cannot make DPDA with empty stack for CFL without prefix property. 

But above example forms a contradiction. Please resolve my doubt. I am getting confused.

Comments

Can it be converted to final state accepting dpda?

it should have

 

idea:-

1) make initial state (Q₀) as final due to accept epsilon

2) on getting 'a', on empty stack, push and go to Q1, make self loop on 'a' on Q1, on getting 'b', pop and change the state Q2, make self loop of 'b' with stack operation is pop on Q2, if 'a' get on Q2 go state Q1 with stack operation push.

 

3) on getting 'b', on empty stack, push and go to Q3, make self loop on 'b' on Q3, on getting 'a', pop and change the state Q4, make self loop of 'a' with stack operation is pop on Q4, if 'b' get on Q4 go state Q3 with stack operation push.

( Note that Q2 and Q4 are final states )

---

i think there has to be separate final states from q2 and q4 on epsilon transistion and empty stack.

please recheck it once.

---

i don't have epsilon transition due to it is DPDA,

The DPDA i gave is for Final state Acceptance not for empty stack acceptance.