我怎么能一眼就看出一种语言是上下文无关的？
How can I tell that a language is context-free from first sight?
我的教授希望我们快速判断给定的语言是规则的、上下文无关但不规则的还是非上下文无关的（换句话说，不画 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
的反向
- 计算一个字母与另一个字母的数量，如 "words with an equal number of a and b" 或 "words with 5 more a than b"
CF 不能做的典型事情：
- 同时在三个地方数数，如a^n b^n c^n
- 在两个交叉的地方同时计数两次，如 a^n b^m a^n b^m
- 像 ww 这样的两个有序副本
- 像"words with an equal number of a, b, and c"一样比较三个字母的数字。
考虑到这些模式，您应该能够确定最常见示例语言的上下文无关性。
我的教授希望我们快速判断给定的语言是规则的、上下文无关但不规则的还是非上下文无关的（换句话说，不画 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 的反向
- 计算一个字母与另一个字母的数量，如 "words with an equal number of a and b" 或 "words with 5 more a than b"
CF 不能做的典型事情：
- 同时在三个地方数数，如a^n b^n c^n
- 在两个交叉的地方同时计数两次，如 a^n b^m a^n b^m
- 像 ww 这样的两个有序副本
- 像"words with an equal number of a, b, and c"一样比较三个字母的数字。
考虑到这些模式，您应该能够确定最常见示例语言的上下文无关性。