#StackBounty: #formal-languages #context-free #lr-k DCFL with prefix property have LR(0) grammar?

Bounty: 50

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 ngeq0}$

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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.