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

I didn't get how you conluded 1st one us true

To become one to one correspondance it should be both One to one and onto,so if we take LL(k) grammars on one side DCFL's on other side how can we conclude

Justify your ans !!

---

@sudsho find LL(1) grammer for  L={ab,aab,aaab......} ...u got 2 know ur answer

---

@Sudsho. Your first argument is correct since due to left factoring, LL(K) is deterministic.

But, your second argument is inappropriate. The grammar is LR(K) as  given. So, it cant be ambigious.

---

@Sudsho. Yes, u r right. There can be CFL's that are ambigious but not LR(K).

---

@prajwal..one to one correspondance here emans that u should have LL(1) grammar for every DCFl..which is of course true since DCFL is not inherently ambiguous..we can do it in linear time

@sushant second statement saying for every CFL u should have LR parser..what if CFL is ambiguous..how will LR will parse?

---

Yes, got it.

---

@sudsho

Is this true ? 

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

I mean For ex: Take a DCFL : $a^n\bigcup a^nb^n$ but it has no LL(K) grammar.

---

@Kapil. Do left factoring. You will get DCFL

---

@Sushant Gokhale

How ? Can you show ?

---

S-> aB | aTb

T-> aTb | ab

B->aB | a

 

left factoring , we get:

S->X M

M->B | Tb    ........doneleft factoring for S

T -> X Y

Y-> Tb | b   ..........done left factoring for T

and so on for B.

---

X->a

---

@sushant that is nt true....
kapil u r right this have no ll(k) grammar for it

---

@Sourabh.

Whats wrong with my left factoring?

---

yes it seems fine sushant

---

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

---

@Sourabh.

When 'b' start appearing  you never return to 'a' .

Also, if no 'b''s appear, you can start popping until the stack goes empty.

 

So, this is deterministic.

---

@Sushant

Check the link first. This has already been proved.

---

Yeah. I think because we cant have recursive left factoring.  Thanks all

---

Kapil, According to me : first statement says if a grammar is LL(1) then it generates a unique DCFL.  (but i doubt about unique DCFL)

But converse that "every DCFL has a LL(1) grammar is not true"

---

@mcjoshi. You are right

---

@mcjoshi. If an LL(K) generates more than 1 DCFL, doesnt it mean non-determinism at some point? I think so

---

For example :Consider two grammars

$S \rightarrow aB$

$B \rightarrow a$

and Grammar $S \rightarrow aa$

first statement is : if a grammar is LL(1) then it generates a unique DCFL. Both grammars above are LL(1) but generate same DCFL (not unique)

It makes me think first statement is false, or Iam misinterpreting something.

---

thanks fr the edit @kapil :)

---

^ is option a valid acc 2 defn of one to one correspondence
In mathematics, a bijection, bijective function or one-to-one correspondence is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set

---

yes sourabh u r right...first one doesnt satisfies one to one correspondance definition..thankyou :)

---

Every CFL need not have a unique CFG.

---

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.