设 L 是由字母表 {0,1} 上包含相同数量的 1 和 0 的字符串组成的语言。
例如:
000111
10010011
10
1010101010
如何证明 L 不是常规语言？
最佳答案
我认为您可以使用与证明 {0^n 1^n: n > 0} 不规则的参数完全相同的参数，因为您可以自由选择与泵引理相矛盾的字符串。
假设 L 是正则的。因此它必须满足某个整数 n(泵浦长度)的泵浦引理。取字符串 S=0^n 1^n ，属于L。根据引理，它可以拆分为S=xyz与 |xy| <= n , |y|>0 , 和 x y^i z属于 L，对于所有 i>=0 .观察 y必须仅包含零。现泵y ，而你只是在字符串中添加零，它不再属于 L。所以你有一个矛盾。所以 L 不是正则的。
关于regex - 显示 count(1s) = count(0s) 的位串不规则，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10672996/