如果L的字符串由0组成只证明L*是正则的
If the string of L consists of 0's only prove that L* is regular
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 整除的单词。
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 整除的单词。