There are two important theorems about LR(k) grammars and DCFL. Mentioned here.

  1. A language has an LR(1) grammar iff it is DCFL.
  2. A language has an LR(0) grammar iff it is DCFL and has prefix property.

I have counter example for 2nd theorem, plz see if it is valid counterexample. (Ofcourse its not valid and I am wrong, But what wrong I am doing here ?)

DCFL without prefix property: $\{b(ab)^n \mid n\geq0\}$

2nd theorem says it should not have $LR(0)$ grammar, but here it is-

$ S \rightarrow Sab \\S \rightarrow b$

PS: This is my first question here, sorry if I violated any protocol.

  • $\begingroup$ Why do you think your grammar is LR(0)? $\endgroup$ Jan 9, 2017 at 14:22
  • $\begingroup$ @YuvalFilmus I took this example from "LR Parsing: Theory and Practice By Nigel P. Chapman" page 69 (books.google.co.in/…) $\endgroup$ Jan 9, 2017 at 14:35
  • 1
    $\begingroup$ Hm. In Sipser's book, he says that every DCFL has an LR(0) grammar... $\endgroup$
    – xavierm02
    Jan 10, 2017 at 0:22
  • $\begingroup$ I have another book that says that LR(0) and finite implies the prefix property. (In fact, they prove that if for two non-empty words $u$ and $v$, both $u$ and $uv$ are in $L$, then $uv^n$ is in $L$ for every $n$) $\endgroup$
    – xavierm02
    Jan 10, 2017 at 0:31
  • 1
    $\begingroup$ yes, we are. We are giving the language prefix property and using LR(0) parser. As per definition the language should not have LR(0) grammar, but with a slight modification we can get an LR(0) grammar. I do not think a question like "is this language LR(0)" will come in any standard examination for this or similar languages as that depends on the definition being used. In literature there are many things like this - a good examination avoids them whereas a bad examination concentrates on them :) $\endgroup$ Feb 2, 2017 at 21:16

2 Answers 2


Your grammar is $\mathrm{LR}(0)$ by adding a $\mathrm{\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\$$ when constructing the $\mathrm{LR}(0)$ automaton (and it is a standard construction).

Omitting syntactical purposes, every DCFL $\mathrm{L}$ can be parsed by an $\mathrm{LR}(0)$ grammar for $\mathrm{L}\$$. What makes $\mathrm{LR}(k)$ ($k>0$) more practical is that it may include more syntactical information which is very important in compiler design. Otherwise, all these techniques would never be used in practice. In that case, $\mathrm{LL}(k)$ with local manipulation for expressions would be used instead, even with prohibitive cost of time and space.


As an conceptual understanding we can think of it as the grammars which satisfies prefix property can be reduced without even using look ahead as those can be accepted by DPDA which accepts through empty stack, but if language is not satisfying the prefix property we will have to check whether the look ahead is $ or any character, if its $ then we can reduce it otherwise we will have to scan input further. DPDA(empty stack acceptance) is less powerful than DPDA(final state acceptance), thats why LR(0) is less powerful than LR(1) Hope this helps.


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.