顯示count（1s）= count（0s）的位串不是常規

Question

設L是由包含相同數目的1和0的字母表{0,1}上的字符串組成的語言。

例如：

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只能由零組成。現在泵y，你只是給字符串加上零，而不再屬於L.所以你有矛盾。所以L不規則。

Answer 2

我不知道一個正式的證明，但直覺是你不能構造一個DFA來識別這種語言（考慮到它需要一個無限數量的狀態來跟蹤111...111000...000或類似的字符串）。

Answer 3

形式證明可以用泵引理的正規語言給出如下：

假設語言是有規律的。所以它必須滿足常量整數p的抽水引理。假設s是任何具有相同數量的0和1的字符串。則S可分爲3個部分，X，Y，Z，使得|xy|<=p，|y|>0，然後x(y^i)z，其中i>=0也應屬於L.

讓我分開的字符串如下：

• y是字符串的一部分，其數量不等於0和1。
• x可能是y之前s的子串。
• 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的值。