**Problem Detail:**

In the familiar book of *Theory of Computation* by *M. Sipser*, the author proved that for *endmarked* context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ (denoted as LR(k) languages) *is* the set of deterministic context-free languages (denoted as DCFL).

My question is also about the relation of those two sets, but in the broader field of all context-free languages. Specifically, *are LR(k) languages and DCFLs equivalent?* And, in which book can I find a proof?

For now, I just have some surrounding facts as followed. Also in the book, the author proved that LR(0) languages *strictly* belong to DCFLs, and LR(k) languages belong to DCFLs for all $k \in \mathbb{N} \setminus \{0\}$. In addition, it's obvious that LR(a) languages belong to LR(b) languages for all $0 \le a < b$. Recently, I've got an unchecked fact from here: LR(1) languages and DCFLs are equivalent.

###### Asked By : Vincent J. Ruan

###### Answered By : Yuval Filmus

According to Wikipedia:

- For every fixed $k \geq 1$: A language has an LR($k$) grammar iff it is DCFL.
- A language has an LR(0) grammar iff it is DCFL and has the prefix property (no word is a prefix of another word).

The first property is proved in Knuth's original paper, in Section V on page 628.

Question Source : http://cs.stackexchange.com/questions/64717

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback