HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cupstackoverflowprogramming

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#60007, answer score: 2

Revisions (0)

No revisions yet.