automata - 我如何从第一眼就看出一种语言是上下文无关的？

Question

我的教授希望我们能够快速判断给定的语言是否是常规的、上下文无关的但不是常规的，或者不是上下文无关的(换句话说，无需绘制 PDA、编写上下文无关语法并使用泵)上下文无关语言的引理)。

我知道一些技巧可以帮助我们快速辨别什么是常规语言，但不知道一种语言是否是上下文无关的。

谢谢。

Answer 1

当然，没有通用的答案。但 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 数量相等的单词”。

考虑到这些模式，您应该能够确定最常见示例语言的上下文无关性。