# Can any language be modeled as LR(k)

If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? If that is possible can it be generalized to all possible languages or just a subset?

• Is this homework? – Marcin Jan 18 '12 at 18:26
• no its not, i am not even in school i was having a discussion with my friend and this question came up :) – Mike G Jan 18 '12 at 18:31
• I'm rather surprised this question got moved to cstheory. The faq says "research-level" questions. – ccoakley Jan 18 '12 at 21:54
• One of the things you nearly always learn when you get taught the concept of languages and grammars is how to remove left-recursion from certain context-free grammars to make them LL(1), thus giving an example of a grammar that is not LL(1) but describes an LL(1) language. This is a big hint the same thing is probably true for LR(1). As another example, consider this language: S := S S, S := a. This language is simply the regular language 'a a+', but as the grammar is ambiguous it is not LR(k) for any k. I therefore think the migration was not warranted: this is far from research-level. – Alex ten Brink Jan 19 '12 at 1:29

You can mechanically transform an LR(k) grammar into an LR(1) grammar (source)

This is not true for LR(*) grammars (k=inf). However, that statement doesn't mean that there isn't such a grammar for the same language. You might just need to rewrite the grammar.

Grammars exist that cannot be transformed, however. Languages for Context-Sensitive grammars can be more expressive than context-free grammars (can only be recognized by linear-bounded automata). Therefore, your hoped-for translation is possible for just a subset.

Update for clarification:

There are languages that can not be represented by LR grammars but do have a grammar that is not LR (the language requires something more powerful than LR). There are also grammars that are not LR that recognize a language that can be recognized by an LR grammar (the language just happens to have a complex grammar, but it is not required).

• I think you have misread the question, i was asking if we have a grammar that is not LL nor LR parsable lets call it A can we have another grammar that is parsable by LR(1) and the Language of that LR grammar is the same as the language of grammar A – Mike G Jan 18 '12 at 18:30
• @MikeG: I've tried to clarify. If A happens to be a Context-Sensitve grammar for a language that requires an LBA, then no LR grammar exists for that language. If A happens to be a Context-Sensitive grammar for a language that is actually a simpler language, then an equivalent LR grammar can exist. So you have a set of grammars that can be simplified and a set of grammars that cannot. Or, you have a set of languages that can be recognized by LR grammars (and permit grammars that are more complex than LR) and a set that cannot. – ccoakley Jan 18 '12 at 18:41

Explanation 1: if you know which $k$ it shall be, you can easily check if the grammar is $LR(k)$ and thus derive an $LR(1)$ Grammar for it. On the other hand you cannot even know if there is a $k \geq 0$ such that $G$ is $LR(k)$.

Different with "Yes and No":

Yes: $L(G_1)$ is deterministic, then it is immediately $LR(k)$ and thus $LR(1)$. No: $L(G_1)$ is not deterministic. This means the language itself is inherently ambiguous this in turn means that there is no Grammar $G_n$ which is not ambiguous.

Much more and much more detailed (and quite understandable, far better than I am able right now) can be found in the following two works. The second contains (iirc) the proof that $LL(k)$ is a (theoretically) weaker than $LR(k)$.

Knuth, D. E. (1965). On the translation of languages from left to right.

D. J. Rosenkrantz and R. E. Stearns. 1969. Properties of deterministic top down grammars.

• "$L(G_1)$ is not deterministic. This means the language itself is inherently ambiguous." No, there exist non-deterministic languages that are not ambiguous; for instance $\{ww^R\mid w\in\{a,b\}^*\}$ the set of even-length palindromes is generated by the unambiguous grammar $S\to aSa\mid bSb\mid\varepsilon$. – Sylvain Nov 10 '13 at 14:48