True or False Question regarding DPDA and prefix property

Question

a) A DPDA which accepts by empty stack cannot accept all Regular Languages?

b) All Regular Languages doesn't satisfy prefix property?

Comments

a. is false and DPDA is DCFL which has more power than regular languages.Infact DPDA is FA+Stack.So FA part can accept all regular languages

I am not able to get the b part.Question is not clear to me.

---

@Warlock lord Brother, kindly share your insight.

---

@Habibkhan Sir, you too please pitch in.

---

@Arjun sir,

L = { a , b } this is finite , so also regular and it satisfies prefix property.

So we cannot say that all all regular languages doesn't satisfy prefix property, some regular like this satisfy prefix property.

Please let me know sir where am I missing.

Answer 1

a. True. Reason explained later.
b. True. Simple example $L = \{a, aa\}$. 

Prefix property requires that if a string $w$ is in $L$, then no prefix of $w$ is in $L$.

So, for above language, $a$ is a prefix of $aa$ and both are in $L$ violating the prefix property. And $L$ is a regular as well as finite language. 

Now, a language is DCFL and accepted by a DPDA with empty stack it must have the prefix property. This is because to accept a string stack must become empty. Now, when the stack becomes empty it must accept the string and due to determinism, it cannot have another move possible. So, no more characters from the input can be accepted. This is the reason why 'a' is TRUE. But the same property is not relevant for DPDA which accepts by final state. So, 

1. Power of DPDA which accept by final state is more than that which accepts by empty stack
2. Power of PDA (which includes non-deterministic) which accept by final state is same as that which accepts by empty stack.

Comments

Arjun sir,Please see this rough state diagram for the example you gave.I tried to build DPDA for my understanding.The transtion from from 2-3 and 2-4 are creating choice which is not allowed for DPDA,is it correct to understand this?

---

@arjun sir , i think this solution is wrong regarding prefix property.

https://gateoverflow.in/135555/prefix-property

Option $(B)$too will not follow prefix property.

As $B=(a+b)^{*}$ 

---

All regular languages doesn't satisfy prefix property.

This statement is a bit ambiguous.

Anyway, Correct answer will be:

Some Regular languages satisfy Prefix Property, Some don’t. 

Answer 2

1. False as every regular language is DCFL , hence a DPDA accepting DCFL by empty stack can also accept regular language .

2. The prefix property for a language is defined as ,

 for all x,y belongs to L, either  x is a prefix of y or y is a prefix of x.

the statement is true as all regular languages does not satisfy prefix property.

ex:  L = (a+b)* ,

a is not prefix of b but a,b belongs to L.

correct me if I’m wrong.

Comments

@AnilGoudar https://gateoverflow.in/377/gate1999_1-6 Read this question, you'll get what I've asked in my above T/F question.

---

Please follow this,

https://link.springer.com/article/10.1007/BF01683274?no-access=true

---

@AnilGoudar Bhai, those are very hi-fi research thing, I'm just a basic avergae student. Anyways, thanks for your time!

Answer 3

Both statements are TRUE.

prerequisite : prefix property. 

Stmt 1: DPDA with empty stack method, accepts those languages which satisfies prefix property. 

Consider a Regular Expression a*, the language corresponds to this regular expression is L={null, a, aa,aaa...},

here, L does not satisfy prefix property and hence cannot be accepte by DPDA with empty stach method.

Stmt 2:    Consider the language L in above explanation.