沒有訂單的語言的抽吸引理

Question

我一直在從我的教科書中練習一些問題來練習總決賽，我遇到了一個我無法弄清楚的問題。基本上它是爲

設L = {w | w包含更多的0比1更多}

它說，作爲一個暗示，正則語言的泵浦引理應該有所幫助。

雖然很容易證明一種語言是非常規的，當有一些模式時，比如0的第一個，然後是1或者回文，因爲你可以通過抽取來打破模式，這裏唯一的要求是這個單詞可以包含0和1以任何順序排列，有更多的0。

我試圖想到一些情況，顯而易見的情況是，如果y = 0，那麼可以將y泵出，直到有更多的0比1爲止。但是我們必須考慮抽象引理被證明是錯誤的每一個可能的情況，只要| xy |只要y可以是任何字符串。 < p（其中p是泵送長度）。 y可以包含0和1，或者只包含1。我在這裏錯過了很明顯的東西嗎提前致謝。

Answer 1

可以選擇像這樣的單詞：
給定數量n，字爲z = 0 ^（2N）1^N，這是在L.
Z = UVW，和| UV | < = n，所以uv只包含零。
因此，v也只包含零，並且| v |> = 1。如果我們假設L是正則的，則由於引理uv^0w在L.
中，但是v = 0^k（k> = 1），所以uv^0w = 0 ^（2n-k）1^n，它不在L中，因爲k> 0。