非常簡單的正則表達式的抽象引理

Question

抽象引理定義（來自wiki）

設L是常規語言。那麼存在一個整數p≥1，僅取決於L，使得長度至少爲p（p稱爲「抽吸長度」[4]）的每個串w可寫爲w = xyz（即，w可以是分爲三個子串），滿足以下條件：

| y | ≥1; | xy | ≤p 對於所有的i≥0，xyiz∈大號

假設我想測試的正則表達式011 既然是定期expressionm，有字符串瓦特至少長度p滿足W = XYZ

的這個自動機的數量是3，p應該是> = 3 但是隻有接受這個自動機的字符串是011 所以我選擇011作爲w 我可以分解3部分011 = xyz 但我該怎麼辦？我無法滿足 | y | ≥1; | xy | ≤p 對於所有i≥0，xyiz∈L

因爲它只接受011 我該如何抽水？我在哪裏錯了

Answer 1

讓p是4.然後有沒有串瓦特在大號長度至少p，這樣的形式「，在大號每串瓦特的任何陳述長度至少爲p [＆hellip;]「將爲vacuously true。所以抽水引理是滿意的。