Zeal Test Series 2018: Theory of Computation - Context Free Language

Question

i am getting a option 

Comments

But i did a question in which it is LL(1) and Lr(1) but not LaLr(1) means the above statement is true only if it is epsilon free LL(1) rit ?

yes

---

And one more doubt i am facing for so many days ---- LR(0) generate the DCFL with prefix property (DPDA with empty stack). (Line said by Arjun sir in discussion part )please give me some references so that I can clear this doubt i couldn't understand that what is dpda with empty stack

---

check this https://gateoverflow.in/256218/self-doubt

Answer 1

option a is answer

we can make only one parse tree for every  string generated by this grammar , moreover the language generated by this grammar is set of all the even length palindrome

so it is unambiguous 

now it is not LL(1)

because  S ⇒ aSa |  bSb |ε 

here the follow of S is a,b ,$  that is match with the first of right hand side 

it means is row S and column a contain 2 entry  and same thing will happen for column b watch the diagram

	a	b	$
S	S->aSa,S->epsilon	S->bSb,S->epsilon	S->epsilon

now the given grammar is not DCFL  so it is not LR(k)

Comments

Gurdeep Saini I have also followed the same approach for first two but as the given grammar is not DCFL  so it is not LL(k) we can directly say ryt

---

1. Each DCFL can be generated by a corresponding LR(k) grammar and each LR(k) grammar generates one DCFL (one-to-one correspondence). 
2. no DCFL is inherently ambiguous.
3. Each LR(k) grammar is unambiguous grammar, but each unambiguous grammar need not to be LR(k). . 
5. An inherently ambiguous language can only be non-deterministic while an non-deterministic language may or may not be inherently ambiguous.

more about DCFL

1) there are some DCFLs which does not have an LL(k) grammar (see ref below).

2) and for any DCFL, we can always have an LR(K) grammar

http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language