代码之家 › 专栏 › 技术社区 › maddie

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

chomsky-hierarchy lr deterministic context-free-grammar theory

1

maddie · 技术社区 · 6 年前

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

这是我们在课堂上讨论的乔姆斯基层次结构,以及识别相关语法的设备:

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

另请注意(如果这个问题应该单独发布,请在评论中告诉我)-线性有界非确定性图灵机与决策者有何不同?

1 回复 | 直到 6 年前

1

templatetypedef 6 年前

这里比较棘手的是,有两个相互关联但并不完全相同的平行层次结构。有LR(k) 语法 ,它们是具有某些属性的语法类。我们知道

LR(0)(&subsetneq;LR(1)和;subsetneq;LR(2)和;subsetneq。。。

也就是说,随着k的增加,越来越多的语法类被包含在LR(k)类中。

独立地,有LR(k) 语言 ,这些语言存在LR(k)语法,可以选择k。Don Knuth有一个很酷的定理表明,一种语言对于某些k有LR(k)语法,当且仅当它有LR(1)语法。因此,从这个意义上讲,LR(k)语言是“可以生成LR(1)语法的语言”

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

那么这对语言的层次结构意味着什么呢?它看起来是这样的,从最不强大/最具限制性到最强大/最不具限制性:

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