patternMinor
Are LR(k) languages and DCFLs equivalent?
Viewed 0 times
dcflsequivalentarelanguagesand
Problem
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.
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.
Solution
According to Wikipedia:
The first property is proved in Knuth's original paper, in Section V on page 628.
- 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.
Context
StackExchange Computer Science Q#64717, answer score: 8
Revisions (0)
No revisions yet.