乔姆斯基层次结构：LR(k) 文法与确定性 CFG？

Question

我们正在学习计算机科学导论课程中的乔姆斯基层次结构。我的教授多次提到 lrk 文法，但书中没有讲授。根据我的理解，它们是生成明确语言的确定性上下文无关语法的子集。但它们与确定性 CFG 有何不同？

这是我们在 class 中使用识别相关语法的设备查看的乔姆斯基层次结构：

recursively enumerable - all turing machines
recursive - deciders/TMs that halt on every input
context sensitive - Linear-bounded non-deterministic Turing machine
context free - nondeterministic PDA
deterministic context free - deterministic PDA 
LRK grammar - deterministic PDA
regular - DFAs/NFAs

单独说明（如果这个问题应该分开，请在评论中告诉我 post）- 线性有界非确定性图灵机与决策者有何不同？

Answer 1

这里的棘手之处在于，有两个相关但不完全相同的平行层次结构。有 LR(k) 文法，它们是具有某些属性的文法 classes。我们知道

LR(0) ⊊ LR(1) ⊊ LR(2) ⊊ ...

也就是说，随着 k 的增加，classLR(k) 中包含越来越大的 classes 语法。

独立地，有 LR(k) 语言，这些语言对于某些 k 的选择存在 LR(k) 文法。 Don Knuth 有一个很酷的定理，它表明一种语言对于某些 k 具有 LR(k) 文法当且仅当它具有 LR(1) 文法时。所以从这个意义上说，LR(k) 语言是 "languages for which you can make an LR(1) grammar."

然后是确定性上下文无关语言 (DCFL)，您可以为这些语言构建确定性 PDA。众所周知，DCFL 与 LR(k) 语言完全相同——也就是说，当且仅当存在 LR(1) 语法时，一种语言才是确定性 CFL。

那么这对于语言的层次结构意味着什么？它看起来像这样，从最不强大/最受限制到最强大/最不受限制：

常规语言
- 由右线性文法、左线性文法、DFA、NFA、正则表达式和前缀文法描述
确定性 CFL
- 由确定性 PDA 和 LR(k) 语法描述
（不确定的）CFL
- 由（非）确定性 PDA 和 CFG 描述。
上下文相关语言
- 由线性有界自动机和上下文相关文法描述
递归语言
- 某些决策者接受的语言，语言和补语都是递归可枚举的语言
递归可枚举语言
- 无限制语法的语言；图灵机的语言；可以被图灵机验证的语言；普查员的语言；等等

乔姆斯基层次结构：LR(k) 文法与确定性 CFG？

Chomsky Hierarchy: LR(k) grammars vs Deterministic CFGs?

theory

deterministic

context-free-grammar

lr

chomsky-hierarchy