5

ポンピング補題の問題について助けが必要です。

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

これは私がこれまでに得たものです：

y = uvw is the string from the pumping lemma.

y = abbc^n とし、n はポンピング補題からの長さです。a:s の数が b:s の数よりも少なく、b:s の数が c:s の数よりも少ないため、y は L にあります。

u = a、v = bb、w = c^n とします。|紫外線| < y、ポンピング補題で述べたとおり。「ポンプ」(bb)^2 すると、次のようになります。

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

これは正しいですか ？私は「正しい道」を進んでいますか？

ありがとう

4

1 に答える 1

7

Lポンピング補題の主なアイデアは、用語の数が無限の正規言語を使用している場合、その言語には永遠に繰り返されるパターンがあることを伝えることです。

その言語に関連付けられている正規表現には、KLEENE-STAR（pattern）が含まれます。

その正規表現（および言語）に関連付けられたオートマトンには、ループが含まれます。

証明は鳩の巣原理を使用して行われます。

これ画像は非常に示唆的です。

この場合、すべての項はq0で始まり、qnで終わる必要があることに注意してください。したがって、言語を定義するオートマトンは有限（最大N状態）であるため、状態の数は限られていますが、単語（つまり用語）は>N文字を持つことができます。鳩の巣原理は、2回到達する状態が存在する必要があることを示しているため、その状態ではループが存在します。

あなたの記法では、あなたは画像との対応をすることができます：

  • あなたuはx画像からです

  • vy画像にあります

  • wz画像からです

q0からに到達するqnには、セットの任意の文字列を使用できます{ uw , uvw, uvvw, uvvvw, ... }。

この特定のケースでは、パターンPはyであり、セットXは{xz xyz xyyz xyyyz ...}であり、Sですlength(x)+length(y)。

于 2012-11-16T03:17:56.333 に答える