Cheap and Secure Web Hosting Provider : See Now

# [Answers] Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

, ,
Problem Detail:

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}\}$.

#### Answered By : Peter Leupold

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.