self-doubt

Question

DPDA with empty stack accepts languages which satisfies prefix property.

{a,aa,aaa} - This can be accepted by pda with empty stack as well as pda with final state as pda with empty stack and final state have same power, but this won't be accepted by DPDA with empty stack.

Every string has prefix epsilon right?

so for L={aⁿbⁿ , n$\geq 0$}as epsilon is a prefix for every string we can't draw a DPDA with empty stack right? as the language is not following prefix property.

Comments

@Utkarsh

Proper prefix of a string is all the prefixes except the string itself. So it includes ∈.

So by the definition of prefix property, proper prefixes are not considered otherwise no language would have had this property.

I don't know how I got confused with the definition and thought proper prefix doesn't include ∈. :P

Let the language L be a*. Then the strings are {∈,a,aa,aaa,...}.

Prefix(a)={∈} which belongs to L.

Prefix(aa)={∈,a} which belong to L.

Now if I append # (Dollar symbol is causing some issue so I use hash) to every string then the language L becomes: {#,a#, aa#,aaa#...}

Prefix(a#)={∈,a} which do not belong to L.

Prefix(aa#)={∈,a,aa} which do not belong to L.

---

@Swapnil

I edited my previous comment on prefix property. Kindly read my last two comments.

---

yeah I got the concept thanks