self doubt

Question

L1 = {aⁿbⁿ / n>=0} 

L2 = {aⁿbⁿ / n >=1} here both are DCFL but L1 is not be accepted by stack  but L2,L1 is accepted by final state right or wrong??

Answer 1

PDA, where acceptance is by an empty stack, is as powerful as PDA with a final state (Acceptance by final state). Means a CFL can be accepted by both PDA with empty stack and PDA with final state. But this is not true with DPDA. (Deterministic Push Down Automata).

The set of languages accepted by DPDA with an empty stack is the proper subset of the set of languages accepted by DPDA with final state.

A language which doesn't have the prefix property, can't be accepted using DPDA with an empty stack.

L = {a, aa}, this don't possess prefix property because 'a' is the prefix of 'aa'. Hence it can't be accepted using DPDA with an empty stack.

L = {$a^n$$b^n$ , n >= 0} also don't possess the prefix property because $\epsilon$ will be the prefix of every other string. Hence it is also not accepted by DPDA with an empty stack.

But L = {$a^n$$b^n$, n>=1} possess the prefix property. Here no string is the prefix of any other string. So it can be accepted by both DPDA with empty stack and DPDA with final state.

Comments

@hement

L2 = {caⁿbⁿ / n >=1} what about this one??

---

@abhishek, try to find the string which can be a prefix of any other string. Here there is no such string. So it can be accepted using  both DPDA with empty stack and DPDA with final state.