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

Question

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

Answer 1

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

等效的构造是 pushdown automaton .它与 DFA 相同，但有一个可用的堆栈。它可能比语法更容易构建。

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

如果你开始怀疑语言是否是上下文无关的，你应该使用所谓的 "pumping lemma for context-free languages" .它描述了所有上下文无关语言的一个属性，如果你的语言违反了它，那么它绝对不是上下文无关的(参见维基百科的 usage notes)。

这个引理是 Ogden's lemma 的推论.所以 Ogden's 更强大，如果你未能应用泵引理，你可以尝试 Ogden's(它的使用方式相同)。