Hopcroft和Ullman的自动机理论导论中的问题4.2.10。原始语言L也可以是非常规的。
假设我们得到0 ^（2 ^ n + 5），n> = 0的函数，你怎么证明（0 ^（2 ^ n + 5））*是正则的？而且对于更一般的情况，当f（0）可以是任何函数？
假设L包含两个字符串0 ^ n和0 ^ m，并且n和m没有共同的因素：它们是相对素数。然后，通过将一些0 ^ n的实例与一些0 ^ m的实例连接起来，可以形成任何长度为（n-1）（m-1）的字符串。因为L *因此必须只排除有限数量的单词，所以补语（L *）'必须是有限的，因此是有规律的;因为常规语言在补语下是封闭的，所以L *也必须是正则的。
（n - 1）（m - 1）来自哪里？嗯，这是coin problem的一个特例（n = 2），我们有一个封闭形式的解决方案。你应该能够研究这个并找到一些证据。
如果L中的所有字符串都有一些可被GCD整除的长度，比如g？嗯，规律性的证明非常相似;考虑修改后的字母表，其中0被符号（0 ^ g）替换，然后证明该字母表上的类似语言是如上所述的常规语言。换句话说，你可以证明L *只包含可被g整除的字符串，所有可被g整除的字符串至少为（n / g - 1）（m / g - 1），其中n和m具有GCD g。这种语言是规则的，因为它只排除了有限多个单词，其长度可以被g整除。