regex - 显示带有 count(1s) = count(0s) 的位串是不规则的

Question

令 L 为由字母表 {0,1} 上的字符串组成的语言，其中包含相等数量的 1 和 0。

例如：

000111
10010011
10
1010101010

你如何证明 L 不是常规语言？

Answer 1

我认为您可以使用完全相同的参数来证明 {0^n 1^n: n > 0} 不规则，因为您可以自由选择与抽水引理相矛盾的字符串。

假设 L 是正则的。所以它必须满足某个整数 n（泵送长度）的泵送引理。取属于 L 的字符串S=0^n 1^n。根据引理，它可以被拆分为S=xyz，|xy| <= n，|y|>0并且x y^i z属于 L ，对于所有i>=0。请注意，它y必须仅包含零。现在 pump y，你只是在字符串中添加零，它不再属于 L。所以你有一个矛盾。所以 L 不是正则的。

Answer 2

我不知道正式的证明，但直觉是你不能构造一个 DFA 来识别这种语言（考虑到它需要无限数量的状态来跟踪表单111...111000...000或类似的字符串）。

Answer 3

可以使用常规语言的泵引理给出正式证明，如下所示：

假设语言是规则的。所以它必须满足 const 整数 p 的泵引理。设s0 和 1 数量相等的任意字符串。那么 s 可以分为 3 部分 x,y,z 使得|xy|<=p, |y|>0, 那么x(y^i)z, wherei>=0也应该属于 L。

让我按如下方式划分字符串：

• y是字符串的一部分，其 0 和 1 的数量不相等。
• x可能是sbefore的子字符串y。
• z可能是之后的部分y。

现在，如果我通过取 来“抽空”字符串i = 0，那么剩下的字符串将是唯一xz肯定会有不相等数量的 0 和 1 的不属于语言 L的字符串。

因此，我们遇到了一个矛盾，因为我们之前假设 L 是正则的。

因此，它是不规则的。

如果理解上述部分有点困难，请考虑一个示例。设 p 为整数 5。设0+1000+11101L 中的字符串。（+ 表示串联）设 x 为“ 0”，y 为"1000"，z 为余数11101。那么如果我们执行x(y^i)z，i=0剩下的字符串将011101不是 L 的一部分。因此是不规则的。

注意：这个例子只是一个让你理解逻辑的例子。不能随机决定 p 的值。