时间戳

首页 > 解决方案 > 乔姆斯基层次结构：LR（k）语法与确定性 CFG？

theory - 乔姆斯基层次结构：LR（k）语法与确定性 CFG？

问题描述

在我的计算机科学入门课程中，我们正在学习乔姆斯基层次结构。我的教授多次提到 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

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

标签： theorycontext-free-grammardeterministiclrchomsky-hierarchy

解决方案

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

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

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

独立地，有 LR(k)语言，它们是存在 LR(k) 语法以选择 k 的语言。Don Knuth 的一个很酷的定理表明，当且仅当它具有 LR(1) 语法时，语言对于某些 k 具有 LR(k) 语法。因此，从这个意义上说，LR(k) 语言是“您可以为其制定 LR(1) 语法的语言”。

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

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

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

推荐阅读