0
$\begingroup$
  • Does $LL(K)$ grammar has one to one correspondence with $DCFL$ ?

If I am understanding right, then the given statement says that $2$ distinct $LL(k)$ have one to one mapping, i.e they should not generate the same $DCFL$.

Let us say:-

$G1 : S-> aB,B->a$ generates $aa$ and $G2: S->aa$ also generates $aa$.

Here, both the grammars are $LL(1)$, and generate the same language $aa$ implying many to one mapping and not one to one .

Moreover, If we take a $DCFL$, $$a^n\bigcup a^nb^n$$, it has no $LL(k)$ grammar for it and another $DCFL$, say $$a^m b^{m+n}$$, then it also has no $LL(K)$ grammar for it.

  • Similarly, I think the statement that "Does $LR(K)$ grammar has one to one correspondence with DCFL" is also false.

Am I right in the reasoning of both the above statements ?

If both are false, then what should be the correct interpretation of the above statements ?

Improve this question
$\endgroup$
2
  • $\begingroup$ The structure and haphazard formatting of your post makes it hard to follow. I'm closing as duplicate because we have a post that answers the bulleted questions. We don't do proofreading, so: do you have a specific questionabout your proof sketch? Of course giving a language in DCFL \ LL(k) shows that the sets are not equal; what's missing is a proof that the proposed language is in this difference of sets. $\endgroup$
    – Raphael ♦
    Apr 23, 2017 at 21:18
  • $\begingroup$ My mistake: the linked question only answers this one together with the rather well-known fact that DCFL = LR(1) = LR(k). $\endgroup$
    – Raphael ♦
    Apr 23, 2017 at 21:23

0

Reset to default