有人可以幫我用這個抽樣引理證明嗎？

我剛開始閱讀關於抽象引理，並知道如何執行一些證明，主要是通過矛盾。只是這個問題我似乎沒有找到答案。我不知道如何開始。我可以假設，必須有抽水長度爲P，並且對於所有w元素L表示LENGTH(w) >= P。當然，我們可以寫出w爲xyz與抽水引理的三個正常條件。有人可以幫我用這個抽樣引理證明嗎？

我必須證明以下語言是非常規：

L = {x + y = z | x,y,z element of {0,1}* and #(x) + #(y) = #(z) }

有人可以幫我在這，我真的想掌握打樣這些類型的問題的過程？

編輯：
對不起，忘了說，字母表是{0,1,+,=}和#表示字符串的二進制值。像#(00101) = 5和#(110) = 6。

來源

2013-03-14 n00b1990

有幾個問題需要澄清：「L」字母表中的「+」和「=」是否是執行數學計算的一部分？＃（x）是否表示x的二進制值？ – DPenner1 2013-03-14 14:33:24

對不起，我忘了說字母是什麼，以及＃的含義。我剛剛編輯了這個問題。 – n00b1990 2013-03-14 15:18:13

@ n00b1990這種語言甚至沒有上下文免費語言（CFL）[**閱讀我的這個答案**]（http://stackoverflow.com/questions/13904309/verifier-of-addition-not-regular-but-is- it-context-free？answertab = votes＃tab-top）讓我知道你是否需要更多的幫助。 – 2013-03-15 15:51:33

既然你想要掌握這個過程，我會在展示證明之前指出一些事情。

要注意的第一件事是，+和=只能出現一次，每個。所以，當你寫你的字符串作爲ww = abc，泵送部分，b，不能包含+或=否則你會到達一個微不足道的矛盾（我沒有使用更標準的w = xyz符號，以避免與L的定義相混淆）。
另一件需要注意的事情是，通常你會選擇一個特定的字符串w進行泵送。在這種情況下，可能更容易挑選共享某個屬性的字符串類。抽象引理只要求你使用一個字符串來達到一個約束，但沒有理由你不能用多個字符串來達成矛盾。

證明（在擾流板）：

因此，讓w在L使得|w| ≥ P和x, y, z不包含前導0的任何字符串。通過抽象引理，我們可以寫w爲w = abc通過抽象引理，我們知道b不是空的。由於b不能包含+或=，因此它完全包含在x, y,或z中。由於x, y, z中只有一個數字是不同的數字（這就是爲什麼我們需要無前導碼0的位），因此二進制方程式中的結果不再存在，導致w與i ≠之間的差異。

來源

2013-03-14 15:50:21 DPenner1

非常感謝您的幫助。我現在知道了。由於方程不能改變，這意味着我們關於語言規則的假設是不正確的，因此它必須是不規則的。我現在明白了，謝謝！幹得好破壞者:) – n00b1990 2013-03-14 21:06:34

雖然我很好奇。如何判斷何時拾取一類字符串比單個字符串更容易？如果b包含'+或='，會發生什麼？這難道不足以達到矛盾，從而證明嗎？ – n00b1990 2013-03-14 21:11:45

至於選擇一類字符串，對我而言稍微容易一些，因爲我的思維過程是：「現在我需要抽b，這樣數字纔會變化。」並且總是滿足的是那些沒有前導零的元素。所以現在我知道了，我真的不需要找到一個特定的字符串，這只是一個額外的步驟。然而，就像@ Patrick87所做的那樣，挑選特定的字符串仍然是完全有效的，並且根據您的思維過程，可能會更容易。 – DPenner1 2013-03-15 01:59:56

選擇字符串1(0^n+1) + 1(0^n) = 11(0^n)。

換句話說，你的字符串將會讀出「兩個和冪n + 2加上兩個加上冪n + 1的和等於11跟n個零」。

由於要抽取的字符串將完全由第一個加數的符號組成，因此抽吸必須更改所表示的數字（向數字添加或移除數字會更改數字;這是因爲我們的字符串不包含前導零），如果x + y = z成立，則x' + y = z不成立，如果x' != x（至少是整數）。

由於抽運引理要求抽運字符串在語言中，並且抽這個字符串失敗，所以我們認爲語言是不規則的。

來源

2013-03-14 16:51:33 Patrick87

我部分理解你的解釋，但你能告訴我爲什麼字符串是必要的嗎？或者這是一類字符串？我感謝您的幫助 – n00b1990 2013-03-14 21:08:52

@ n00b1990這是一類以您的語言編寫的抽象引理失敗的字符串。使用抽象引理的證明通常是這樣的：抽吸引理說明一定長度的所有字符串應該是可抽取的;這裏至少有一串長度;它不是可以抽水的;假設語言滿足抽詞引理是錯誤的;該語言不規則。 – Patrick87 2013-03-14 21:17:52

有人可以幫我用這個抽樣引理證明嗎？

回答

相關問題