如何 L = {a^n b^m | n,m>=1, n != 3m} 不正则？
How L = {a^n b^m | n,m>=1, n != 3m} is not regular?
我正在努力理解这个问题。
有人有什么想法吗？
编辑：
它是 ...n,m<1...，但我的问题是 ...n,m>=1...
如果 n 和 m 小于或等于 1，则该语言实际上是正则的，因为它是有限语言 {a, b, ab}。相反，如果您的意思是 n 和 m 大于或等于 1，则分析变得更加困难。
假设n和m大于等于1，语言是无限的，可能是正则的，也可能不是正则的。我有一种感觉，使用常规语言的抽水引理很难或不可能证明这种语言是非常规的。这里有两种更简单的证明方法：Myhill-Nerode 定理和常规语言的闭包属性。
为了使用 Myhill-Nerode 证明该语言是非常规的，我们需要确定一个无限的字符串序列，这些字符串对于我们的语言都是可区分的。如果两个字符串具有不同的字符串集，可以将它们连接成我们语言中的字符串，那么这两个字符串在我们的语言中是可区分的。考虑字符串 aaa、aaaaaa、...、a^3k、...。在我们的语言中不能连接到这些以得到字符串的最短字符串是 b, bb, …, b^k, … 。这意味着每个字符串 a^3k 对于我们的语言都是可区分的；可以连接到我们的字符串的字符串集取决于参数 k。这表明对于我们的语言，在不可区分关系下有无限多个等价类。这意味着我们语言的最小 DFA 将具有无限多个状态，这是一个矛盾。
要使用闭包属性证明语言是非常规的，请考虑以下语言：
L = {a^n b^m | n, m >= 1, n != 3m}
R = {a^n b^m | n, m >= 1, n = 3m}
S = {a^n b^m | n, m >= 1}
首先，请注意 R 是非正则的（使用抽水引理可以简单地证明这一点）并且 S 是正则的（这是正则语言 aabb）。
接下来注意S\L=R（这里\表示集差）
然而，这是一个矛盾，因为我们假设 L 是正则的，我们知道 S 是正则的，并且我们知道正则语言在集合差异下是封闭的（我们可以为两种正则语言的差异构造一个 DFA，使用笛卡尔积机构造）。两种正则语言之差不可能是非正则语言R，故反证L必非正则
这是使用闭包属性显示不规则性的另一种方式。
直觉上，我们期望语言 {a3nbn | n∈ N} 是非常规的，因为它本质上是规范的“a 的 n 个副本，然后是 b 的 n 个副本”语言扩展了一点。如果您对这种语言不规则的想法感到满意，那就太好了！如果不是，您可以使用 Myhill-Nerode 定理或抽水引理对此进行简短证明。
考虑到这一点，语言 L = { anbm | n ≠ 3n } 与上面给出的关系密切相关。事实上，它有点像是上述语言的“对立面”。因此，让我们形成所有未出现在 L 中的字符串的补码 L'。这将是 a3nbn 形式的所有字符串，加上所有不匹配 ab 的字符串。嘿！如果 L 是正则的，那么 L' 也是正则的。
因为 L' 中有一些我们不需要的字符串，让我们将它与 ab 相交以得到我们想要的字符串。将正则语言与正则语言相交返回正则语言，这意味着如果 L’ 是，则 L’ ∩ ab 是正则的。但这种语言就是我们在上面看到的那种语言，我们知道它是不规则的！这意味着 L 也不是，我们完成了！
我正在努力理解这个问题。 有人有什么想法吗？
编辑： 它是 ...n,m<1...，但我的问题是 ...n,m>=1...
如果 n 和 m 小于或等于 1，则该语言实际上是正则的，因为它是有限语言 {a, b, ab}。相反，如果您的意思是 n 和 m 大于或等于 1，则分析变得更加困难。
假设n和m大于等于1，语言是无限的，可能是正则的，也可能不是正则的。我有一种感觉，使用常规语言的抽水引理很难或不可能证明这种语言是非常规的。这里有两种更简单的证明方法：Myhill-Nerode 定理和常规语言的闭包属性。
为了使用 Myhill-Nerode 证明该语言是非常规的，我们需要确定一个无限的字符串序列，这些字符串对于我们的语言都是可区分的。如果两个字符串具有不同的字符串集，可以将它们连接成我们语言中的字符串，那么这两个字符串在我们的语言中是可区分的。考虑字符串 aaa、aaaaaa、...、a^3k、...。在我们的语言中不能连接到这些以得到字符串的最短字符串是 b, bb, …, b^k, … 。这意味着每个字符串 a^3k 对于我们的语言都是可区分的；可以连接到我们的字符串的字符串集取决于参数 k。这表明对于我们的语言，在不可区分关系下有无限多个等价类。这意味着我们语言的最小 DFA 将具有无限多个状态，这是一个矛盾。
要使用闭包属性证明语言是非常规的，请考虑以下语言：
L = {a^n b^m | n, m >= 1, n != 3m}
R = {a^n b^m | n, m >= 1, n = 3m}
S = {a^n b^m | n, m >= 1}
首先，请注意 R 是非正则的（使用抽水引理可以简单地证明这一点）并且 S 是正则的（这是正则语言 aabb）。
接下来注意S\L=R（这里\表示集差）
然而，这是一个矛盾，因为我们假设 L 是正则的，我们知道 S 是正则的，并且我们知道正则语言在集合差异下是封闭的（我们可以为两种正则语言的差异构造一个 DFA，使用笛卡尔积机构造）。两种正则语言之差不可能是非正则语言R，故反证L必非正则
这是使用闭包属性显示不规则性的另一种方式。
直觉上，我们期望语言 {a3nbn | n∈ N} 是非常规的，因为它本质上是规范的“a 的 n 个副本，然后是 b 的 n 个副本”语言扩展了一点。如果您对这种语言不规则的想法感到满意，那就太好了！如果不是，您可以使用 Myhill-Nerode 定理或抽水引理对此进行简短证明。
考虑到这一点，语言 L = { anbm | n ≠ 3n } 与上面给出的关系密切相关。事实上，它有点像是上述语言的“对立面”。因此，让我们形成所有未出现在 L 中的字符串的补码 L'。这将是 a3nbn 形式的所有字符串，加上所有不匹配 ab 的字符串。嘿！如果 L 是正则的，那么 L' 也是正则的。
因为 L' 中有一些我们不需要的字符串，让我们将它与 ab 相交以得到我们想要的字符串。将正则语言与正则语言相交返回正则语言，这意味着如果 L’ 是，则 L’ ∩ ab 是正则的。但这种语言就是我们在上面看到的那种语言，我们知道它是不规则的！这意味着 L 也不是，我们完成了！