automata - 我如何判断一门语言从一开始就与上下文无关？

Question

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

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

谢谢你。

Answer 1

当然，没有普遍的答案。但是有一些 CF 可以或不能做到的通用模式以不同的变体形式出现。CF 可以做的事情（而 REG 不能）：

• 在两个地方同时计数，例如 a^nb^n，
• 也反复喜欢在a^nb^na^mb^m
• 或嵌套在 a^nb^ma^mb^n 中
• 回文模式，即 w 后跟 w 的倒数
• 计算一个字母相对于另一个字母的数量，例如“a 和 b 数量相等的单词”或“a 比 b 多 5 个的单词”

CF 不能做的典型事情：

• 在三个地方同时计数，例如 a^nb^nc^n
• 在两个交叉的地方同时计数两次，例如 a^nb^ma^nb^m
• 两个订购的副本，如 ww
• 比较三个字母的数量，例如“a、b 和 c 数量相等的单词”。

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