大门|大门-CS-2014-（第1组）|问题24

以下哪一项是正确的？

（A） A. （B） B （C） C （D） D 答复: （C） 说明： （A） L={ANBN | n>=0}是不规则的，因为不存在可以 推导出这个语法。直觉上，有限自动机有有限的内存，因此它无法跟踪 as的数量。不过这是一个标准的CFL。

（B） L={ANBN | n是素数}也是不规则的，因为没有办法记住/检查 当前n是否为素数。因此，不存在有限自动机来推导这种语法，因此 这是不正常的。

（C） L={w | w有3k+1bs}是一种正则语言，因为k是一个固定常数，我们可以很容易地 仿效我∗ 文学士∗ …..文学士∗ 这样就正好有3k+1B和a∗ 在每个b的周围 语法。

（D） L={ww | w∈ Σ ∗ } 它又不是一个常规语法，事实上它甚至不是一个CFG。没有 使用有限自动机记忆和导出双单词的方法。

因此，正确答案应该是（C）。 这个解决方案是由 维内特·珀斯瓦尼 .

这个问题的小测验