computer-science - 如何确定一种语言是否与上下文无关？

Question

我怎么知道这些语言是否是上下文无关的？

Answer 1

首先，你应该尝试构建一个上下文无关的语法来形成主题中的语言。如果所有产生式的左侧恰好包含一个非终结符，则文法是上下文无关的。根据定义，如果存在，则该语言是上下文无关的。

等效构造是下推自动机。它与 DFA 相同，但有可用的堆栈。它可能比语法更容易构建。

但是，如果您未能构建语法或自动机，这并不意味着语言不是上下文无关的；或许，只是你自己构建的语法不够棘手（例如，我曾经花了大约 7 个小时来构建一个棘手的语言的语法）。

如果您开始怀疑该语言是否是上下文无关的，则应该使用所谓的“为上下文无关语言抽取引理”。它描述了所有上下文无关语言的属性，如果你的语言违反了它，那么它绝对不是上下文无关的（参见维基百科的使用说明）。

这个引理是奥格登引理的推论。所以奥格登的更强大，如果你没有应用抽引引理，你可以试试奥格登的（它的使用方式相同）。

Answer 2

编辑

正如评论中建议的那样证明一种语言是非 CFG 的，我相信是通过使用 ogdens 引理。我之前的答案中包含的固有误解是可以原谅的:) 为潜伏者保留早期的答案。

旧答案

通过查看使用的语法和规则！从图像中可以看出（由维基百科乔姆斯基层次结构提供）。只有常规语言是非上下文无关的。暗示任何单独使用 A->aB 或 A->Ba 形式的东西的东西都不是上下文无关的。

编辑 A->aB 和 A->Ba 定义旨在表达左右递归语法，而不是按字面意思理解。

Answer 3

您需要该语言的语法来确定它是否是上下文无关的。如果语法的所有产生式都具有“（非终结符）->终结符和非终结符的序列”的形式，则语法是上下文无关的。