World's most popular travel blog for travel bloggers.

Are LR(k) languages and DCFLs equivalent?

, , No Comments
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback