抽吸引理（常規語言）

我需要一些幫助抽取引理問題。抽吸引理（常規語言）

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }

這是我走到這一步：

y = uvw is the string from the pumping lemma.

我讓Y = ABBC^n，n爲從泵引理的長度。 y在L中，因爲a的個數小於b個的個數，而b個的個數小於c個個的個數。

我讓u = a，v = bb和w = c^n。 | UV |如抽吸引理所述。如果我「泵」（bb）^ 2然後我得到

y = abbbbc^n which violates the rule #b(L) < #c(L).

是這樣嗎？我在「正確的道路上」嗎？

感謝

來源

2012-11-16 mrjasmin

您是否正在尋求使用抽象引理來證明描述的語言是正規的？或者它不是經常的？無論哪種方式，您都不會選擇子字符串重複：抽吸引理僅僅說有一些* n *，因此在任何一個句子中* s *的長度> = * n *都有一些* s *變成* uvw *使得| * uw * | <* n *，| * v * | > = 1，* u * * v *^* i * * w *是所有* i *的句子。（因爲'c'在這種語言中總是可重複的，所以你可能會遇到一個挑戰，就是找到一些句子，在句子中，一些內部c的句子不起作用。） –

抽水引理是要告訴你，當你有一個正規語言L的條款的無限數量存在這樣不斷重複的語言模式的主要思想。

與該語言相關的正則表達式將包含KLEENE-STAR（模式）。

與該正則表達式（和語言）關聯的自動機將包含一個循環。

證明是使用鴿子原理完成的。

這是非常暗示。

請注意，在這種情況下，所有術語必須以q0開始並以qn結尾。因此，定義語言的自動機是有限的（最大N個狀態），所以存在有限數量的狀態，但是單詞（即術語）可以具有> N個字母。鴿子原理告訴我們必須有一個達到2次的狀態，所以在那個狀態下會出現一個循環。

在你的符號，可以使相應於圖像這樣：

您u是從圖像
vx是圖像y
w是z從圖片

要從q0到qn，您可以使用集合中的任何字符串：{ uw , uvw, uvvw, uvvvw, ... }。

在這種特定的情況下的圖案是Py，設定X是{xz xyz xyyz xyyyz ...}和S是length(x)+length(y)。

來源

2012-11-16 03:17:56 alinsoar

謝謝你這張圖片。但是，我選擇了一個很好的弦來抽水嗎？ – mrjasmin

抽吸引理（常規語言）

回答

相關問題