我只是在学习编程语言的原理。我知道常规语法和上下文无关语法的概念及其用法。但是我仍然无法确定哪个更强大以及为什么。请帮忙
提前致谢。
问问题
199 次
1 回答
3
每种常规语言都是上下文无关的，但某些上下文无关语言不是常规语言。从这个意义上说，上下文无关语言比常规语言更“强大”。
作为上下文无关的非常规语言的一个示例，考虑由字符 x 和 y 组成的所有回文的语言。您可以使用抽水引理或 Myhill-Nerode 定理证明这种语言是非常规的。但是，它是上下文无关的，因为它是由语法生成的
S → aSa | 锑| 一个 | 乙 | ε
直观地说，常规语言对应于可以在具有有限内存的计算机上解决的是/否问题（Myhill-Nerode 定理是形式化这种直觉的一种方式）。这意味着任何仅靠有限内存无法解决的是/否问题因此不会对应于常规语言。上下文无关语言占据了一个奇怪的中间地带——它们对应于可以在具有有限内存和无限堆栈的计算机上解决的问题。
如果您有兴趣了解更多有关这方面的信息，我建议您阅读有关形式语言和可计算性的书。关于这些语言类别有很多非常漂亮的结果，我无法将其压缩成一个答案。
希望这可以帮助！
于 2014-09-10T01:08:41.987 回答