DCFLs

Question

S1: Every DCFL has unambiguous grammar

S2: Every language accepted by DPDA with final state is also accepted by DPDA with empty stack

S1 is given as true and S2 false.

Explain how?!

Answer 1

S1: Every DCFL has an unambiguous grammar. True [DCFL has at least one grammar which is unambiguous But  DCFG can be ambiguous]

S2: Every language accepted by DPDA with the final state is also accepted by DPDA with the empty stack. False [The set of languages accepted by a DPDA by the empty stack is a subset of the set of languages accepted by a DPDA by final state. Example 0*, 1* which is accepted by final state but not with empty stack since we can only do push but don't know when we start poping]

Comments

Am I correct:

DCFG are always unambiguous.(https://en.m.wikipedia.org/wiki/Ambiguous_grammar)

DCFL are always unambiguous.(https://www.google.com/url?sa=t&source=web&rct=j&url=https://cs.wmich.edu/~elise/courses/cs6800/DCFL.pptx&ved=2ahUKEwiVzdHx8ufrAhVM8HMBHWJeAlcQFjAFegQIBBAB&usg=AOvVaw3BPDAYtQMSLoh9RJV55gEL)

 

---

If you minimize grammar,"ab" will no longer exist in S production

---

https://gateoverflow.in/940/gate-cse-2003-question-51

 

This question is the example of your doubt

Answer 2

Regarding S2: Conversion from Final state to Empty state PDA & vice-versa involves adding epsilon transition. It does not leave DCFL to DCFL but makes it CFL. Thus S2 is false.

Answer 3

S1 is true because DPDA cannot have choice, therefore the grammer will be unambiguous.

For  S2 refer: https://gateoverflow.in/377/gate1999_1-6