I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar:

$$ S \rightarrow Ac \\ S \rightarrow B \\ A \rightarrow aAbb \\ A \rightarrow abb \\ B \rightarrow aBb \\ B \rightarrow ab $$

Which generates the language $\{a^nb^n\}\cup\{a^nb^{2n}c\}$. He states that this language is clearly RL($k$), which is easy to see, and he proves that it cannot be LR($k$). But, in his proof, he states:

The problem is, of course, the appearance of "c" at the extreme right.

So, my doubt is: if it wasn't for the extra "c", could the language be LR($k$)? He remarks that, of course, the problem is the "c", but I don't see how I could write an LR($k$) grammar for $\{a^nb^n\}\cup\{a^nb^{2n}\}$.


Propbably you should read the citation as: "The problem is that the c (which separates the two parts of the language) is at the extreme right and not at the extreme left, where we start parsing."

Therefore it is of no help (unlike the case where you start reading at the right), and therefore there is no LR-grammar for this language. Neither with the c nor without.

| cite | improve this answer | |
  • 1
    $\begingroup$ Right. It's RL(k) because of the $c$ (but not without). $\endgroup$ – Raphael Jun 26 '16 at 11:44
  • $\begingroup$ Oh, I thought I was missing something. Thanks! :D $\endgroup$ – paulotorrens Jun 26 '16 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.