我的教授希望我们能够快速判断给定的语言是否是常规的、上下文无关的但不是常规的，或者不是上下文无关的(换句话说，无需绘制 PDA、编写上下文无关语法并使用泵)上下文无关语言的引理)。
我知道一些技巧可以帮助我们快速辨别什么是常规语言，但不知道一种语言是否是上下文无关的。
谢谢。
最佳答案
当然，没有通用的答案。但 CF 可以或不能执行的一些通用模式会在不同的变体中出现。 CF 可以做的事情(而 REG 不能做):
- 在两个地方同时计数，例如 a^n b^n，
- 也反复像 a^n b^n a^m b^m
- 或像 a^n b^m a^m b^n 一样嵌套
- 回文模式，即 w 后跟 w 的反转
- 计算一个字母相对于另一个字母的数量，例如“a 和 b 数量相等的单词”或“a 比 b 多 5 个的单词”
CF 不能做的典型事情:
- 在三个地方同时计数，例如 a^n b^n c^n
- 在两个交叉对的地方同时计数两次，例如 a^n b^m a^n b^m
- 两个有序副本，如 ww
- 比较三个字母的数量，如“a、b、c 数量相等的单词”。
考虑到这些模式，您应该能够确定最常见示例语言的上下文无关性。
关于automata - 我如何从第一眼就看出一种语言是上下文无关的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40668738/