快速/簡單的正則表達式/正則語言澄清

我覺得自己就像在這裏發佈這樣簡單的問題，但本網站的知識基礎是驚人的。感謝你的理解。快速/簡單的正則表達式/正則語言澄清

關於一個找到的最小長度的泵送（關於泵送引理正則語言）正則表達式的問題：

正則表達式R = 1011（在字母表{0,1}）

是不是唯一匹配這個字符串ε（空字符串）和1011？

編輯 - 我一直盯着太多克萊恩星星。空字符串ε不是這種語言。

正則語言的屬性表明，如果一種語言可以用有限自動機（或正則表達式）表示，那麼它是規則的，當然這個可以由兩者表示。（這個問題顯然導致我相信語言是常規的）

但是另一方面，抽吸引理（非正式地）指出，所有常規語言都有一個抽吸長度，從而所有至少有這個長度的字符串可以被拆分進入xyz，y可以重複，而不會影響結果。 ε不能被定義泵送，並且1011不能被泵送（我不認爲這是個問題），因爲沒有其他字符串匹配它，所以刪除或添加y的實例將導致字符串不被接受/匹配。

我的邏輯錯誤在哪裏？

第二次編輯 - 任何p> 4的答案，可以通過將x或y或z設置爲φ（空集）來抽取語言，當與任何連接時結果爲空集？

2010-09-15 prelic

爲什麼'ε'包含在您的語言中？我錯過了什麼嗎？ – Kobi 2010-09-15 16:36:14

你是對的。謝謝。 – prelic 2010-09-15 17:56:39

抽水引理對於有限的語言並不是很有用。所有語言都是固定的 - 例如，您的情況下，您可以將「抽吸長度」設置爲4.從空白意義上說，可以抽出超過該長度的所有單詞:)

2010-09-15 16:33:36 Kobi

另一個評論是，抽水論是更有用的證明一種語言**不是經常的。我稍後會將它編輯成答案，但我需要去。祝你好運！ – Kobi 2010-09-15 16:42:48

但是爲了抽取任何字符串，它需要被分成xyz（除其他條件之外），y =/=ε。我假設答案是抽水引理的某種漏洞特性。 – prelic 2010-09-15 17:51:36

@prelic - 如果有0個單詞，則可以放心地說*所有單詞都滿足條件。是的，從某種意義上講，我有一點彎曲，但是當我學習邏輯時我們做了。 – Kobi 2010-09-15 17:58:29

回答