令 L 为由字母表 {0,1} 上的字符串组成的语言,其中包含相等数量的 1 和 0。
例如:
000111
10010011
10
1010101010
你如何证明 L 不是常规语言?
令 L 为由字母表 {0,1} 上的字符串组成的语言,其中包含相等数量的 1 和 0。
例如:
000111
10010011
10
1010101010
你如何证明 L 不是常规语言?
我认为您可以使用完全相同的参数来证明 {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 不是正则的。
我不知道正式的证明,但直觉是你不能构造一个 DFA 来识别这种语言(考虑到它需要无限数量的状态来跟踪表单111...111000...000
或类似的字符串)。
可以使用常规语言的泵引理给出正式证明,如下所示:
假设语言是规则的。所以它必须满足 const 整数 p 的泵引理。设s
0 和 1 数量相等的任意字符串。那么 s 可以分为 3 部分 x,y,z 使得|xy|<=p
, |y|>0
, 那么x(y^i)z
, wherei>=0
也应该属于 L。
让我按如下方式划分字符串:
y
是字符串的一部分,其 0 和 1 的数量不相等。x
可能是s
before的子字符串y
。z
可能是之后的部分y
。现在,如果我通过取 来“抽空”字符串i = 0
,那么剩下的字符串将是唯一xz
肯定会有不相等数量的 0 和 1 的不属于语言 L的字符串。
因此,我们遇到了一个矛盾,因为我们之前假设 L 是正则的。
因此,它是不规则的。
如果理解上述部分有点困难,请考虑一个示例。设 p 为整数 5。设0+1000+11101
L 中的字符串。(+ 表示串联)设 x 为“ 0
”,y 为"1000"
,z 为余数11101
。那么如果我们执行x(y^i)z
,i=0
剩下的字符串将011101
不是 L 的一部分。因此是不规则的。
注意:这个例子只是一个让你理解逻辑的例子。不能随机决定 p 的值。