如何确定一种语言是否是上下文无关的？
我如何知道这些语言是否上下文无关？
How can I know whether the languages are context free or not?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
我如何知道这些语言是否上下文无关？
How can I know whether the languages are context free or not?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
首先，您应该尝试构建一个形成主题语言的上下文无关语法。如果所有产生式的左侧恰好包含一个非终结符，则语法是上下文无关的。根据定义，如果存在一种语言，那么该语言就是上下文无关的。
等效的构造是下推自动机。它与 DFA 相同，但具有可用的堆栈。它可能比语法更容易构建。
然而，如果你无法构建语法或自动机，并不意味着语言不是上下文无关的；也许，只是你无法构建一个足够棘手的语法（例如，我曾经花了大约 7 个小时为一种棘手的语言构建了一个语法）。
如果您开始怀疑该语言是否是上下文无关的，您应该使用所谓的“泵引理”对于上下文无关语言”。它描述了所有上下文无关语言的属性，如果您的语言违反了它，那么它绝对不是上下文无关的（请参阅使用说明（维基百科）。
该引理是奥格登引理的推论。所以奥格登的更强大，如果你未能应用泵引理，你可以尝试奥格登的（它的使用方式相同）。
First, you should attempt to build a context-free grammar that forms the language in subject. A grammar is context-free if left-hand sides of all productions contain exactly one non-terminal symbol. By definition, if one exists, then the language is context-free.
An equivalent construct would be a pushdown automaton. It's the same as DFA, but with a stack available. It may be easier to build than a grammar.
However, if you fail to build a grammar or an automaton, it doesn't mean that a language is not context-free; perhaps, it's just you who can't build a grammar tricky enough (for example, I once spent about 7 hours to build a grammar for a tricky language).
If you start to doubt if the language is context-free, you should use a so-called "pumping lemma for context-free languages". It describes a property of all context-free languages, and if your language violates it, then it's definitely not context-free (see usage notes at Wikipedia).
This lemma is a corollary of Ogden's lemma. So Ogden's is more powerful, and if you failed to apply pumping lemma, you might try Ogden's (it's used the same way).
编辑
正如评论中所建议的，证明一种语言是非 CFG 的，我相信是通过使用奥格登斯引理。我之前的回答中包含的固有误解是可以原谅的:)为潜伏者保留之前的答案。
旧答案
通过查看所使用的语法和规则！从图像中可以看出（维基百科乔姆斯基层次结构提供）。只有常规语言是非上下文无关的。暗示任何单独使用 A->aB 或 A->Ba 形式的东西都不是上下文无关的。
编辑
A->aB 和 A->Ba 定义旨在表达左递归语法和右递归语法，不能按字面意思理解。
Edit
As suggested in the comments to prove a language to be non-CFG, I believe is by using an ogdens' lemma. The inherent misinterpretation contained in my earlier answer is to be excused :) Retaining the earlier answer for lurkers.
Old answer
By looking at the grammar and rules used! As seen from the image (courtesy wikipedia chomsky hierarchy). Only regular languages are non-context-free. Implying anything which uses things of form A->aB or A->Ba alone are not context free.
Edit
A->aB and A->Ba definitions are meant to express Left and Right recursive grammars and are not to be taken literally.
您需要该语言的语法来确定它是否与上下文无关。如果语法的所有产生式都具有“（非终结符）->终结符和非终结符的序列”的形式，则该语法是上下文无关的。
You need a grammar for the language to determine if it is context free. A grammar is context free if all it's productions has form "(non-terminal) -> sequence of terminals and non-terminals".