LL(k) grammars

Question

1. LL(k) grammars have one to one correspondance with DCFL's

2. LR(k) grammars have one to one correspondance with CFL's

Which of them is True and explain it bit clearly? 

Comments

is it both true?

---

Ans given as both False,but i feel 1 is atleast true

---

Nice explanation by arjun sir , one can refer this :https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars

---

Yes prajwal,i also did the same... 1 true and another false

Answer 1

1st one is false.....for every LL(1) we can have DCFL but not converse...and hence one to one correspondance is not satisfied(thankyou saurabh)
also we have one to one correspondence of DCFL with LR(k) ..so for every DCFL we can have a LR(k) grammar and vice versa..

Ex : Take a DCFL L = $a^mb^{m+n} | m\geq n$ . Now this language is DCFL, but there is no LL(K) for it .

Ex : Take another DCFL L = $a^n \bigcup a^n b^n$ . Now this language is again DCFL, but there is even no LL(K) for it (thankyou kapil fr the examples)

---

n second statement is saying CFL not DCFL...so chance is there that ur CFL might be inherently ambiguous(means nt having nt even a single unambiguous grammar)..for CFL we have one to one correspondance with CFG not LR(k)..so second is false..

---

Hence, both are false..

Comments

Ex : Take another DCFL $L = \left \{ a^n | n\geqslant 0 \right \} \bigcup \left \{ a^nb^n | n\geqslant 0 \right \}$ . Now this language is again DCFL, but there is even no LL(K) for it (thankyou kapil fr the examples)

 This was asked in GATE 2020, https://gateoverflow.in/333221/gate-2020-cse-question-10

---

How is this language $a^mb^{m+n} | m\geq n$ DCFL??

Since m >=n, it means (m+n) can vary from m<= (m+n) <= 2m

And this is not a DCFL.

---

Lets lets say G1 is a grammar
S->a

and G2 grammar
S->A
A->a

these both grammar are LL(1) .
both will have same DCFL.
so can't be ONE to ONE

and this grammar is also LR(0)
so similarly LR(0) is not ONE to ONE with DCFL

why you are saying LR(K) for ONE to ONE with DCFL ?

Answer 2

 

Further Study Source; Introduction to the Theory of Computation by Michael Sipser.