我刚刚学习了编程语言的原理。我知道规则语法和上下文无关语法的概念及其用法。但我仍然无法决定哪一个更强大以及为什么。请帮助
提前谢谢。
每种正则语言都是上下文无关的，但有些上下文无关的语言不是正则的。从这个意义上说，上下文无关语言比常规语言更"强大"。
作为一个无上下文的非正则语言的例子，考虑由字符x和y组成的所有回文的语言。你可以通过使用泵浦引理或Myhill-Nerode定理来证明这种语言是非正则的。然而，它是上下文无关的，因为它是由语法生成的
S→aSa|bSb|a|b|ε
直觉上，正则语言对应于可以在内存有限的计算机上解决的是/否问题（Myhill-Nerode定理是将这种直觉形式化的一种方法）。这意味着，任何只能用有限内存解决的是/否问题都不会与常规语言相对应。上下文无关语言占据了一个奇怪的中间地带——它们对应的问题可以在内存有限、堆栈无限的计算机上解决。
如果你有兴趣了解更多关于这方面的知识，我建议你通读一本关于形式语言和可计算性的书。关于这些类语言，有很多令人惊讶的漂亮结果，我无法将其压缩为一个单一的答案。
希望这能有所帮助！