如何判断一种语言是否是一见钟情的？

Question

我的教授期望我们能够快速判断一个给定的语言是否是规则的，上下文无关的，但不是常规的，或者没有上下文无关的（换句话说，没有绘制PDA，编写上下文无关文法，并使用抽象引理用于上下文无关的语言）。

我知道提示，可以帮助我们快速判断常规语言一见钟情，但不知道语言是否无上下文。

谢谢。

Answer 1

当然，没有普遍的答案。但是有一些CF可以或不可以做的以不同变体显示的一般模式。事情CF可以做（和REG没有）：同时

• 数在两个地方就像一个^ NB^N，
• 也多次就像在一个^ NB^NA^MB^M
• 或嵌套例如，在“具有相等数量的a和b的单词”中计算一个字母相对于另一个字母的数量或者“具有比a多5个a的词”

个

典型事物CF不能做：同时

• 数在三个地方就像一个^ NB^NC^N
• 计数同时两次都像处在^ NB ^马^ NB的地方有两个交叉对^ m
• 像ww
• 两个有序的副本比较三个字母的数字，如“在a，b和c数目相等的单词”中。

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