如何证明这些是正则语言

Question

所以我有这些问题需要帮助。我必须证明它们是常规语言。我不知道问题3和问题4中的DSQ或DF应该是什么。我有一本书"Spiser的Comp Theory简介"，但我没有发现任何提及DSQ或DF的内容。

1） L={w.…w∈∑*}∑={a，b}

2） Trancate（n）={wa^nw∈∑*a∈∑|w|=n}

3） DSQ＝｛a^p，b^p:p素数｝

4） DF=｛a^n b^n:n>或等于0｝

Answer 1

这四种语言都不是正则的。有几种不同的技术可以用来证明语言是不规则的。这是一个样本：

1. 使用正则语言的pumping引理。这是最广泛使用的证明语言不规则的技术。你提到你有一本Sipser的书，他在第一章中对这个主题做了很好的处理。

2. 使用Myhill-Nerode定理。这个强大的定理比抽运引理更难理解，但作为证明语言不规则的工具，它有双重作用，并提供了一种优秀的直觉，你可以用来嗅出非规则语言。（这是我在CS理论导论中教给学生的技巧）。链接的幻灯片包含{aⁿbⁿ|ninN}不是正则的证明，无论是从第一性原理还是使用Myhill Nerode。

3. 使用正则语言的闭包属性。通过证明，在应用将正则语言映射到正则语言的特定操作后，最终得到的是非正则语言，通常可以证明一种语言不是正则的。

看看你提供的例子，我认为pumping引理将是证明语言（1）是非正则的最简单的途径。Myhill-Nerode定理应该是（3）和（4）的短功。对于（2），您可能需要考虑将语言与b^&stara^&星b^&star，然后将Myhill Nerode或泵浦引理应用于所产生的语言。