問題タブ [pumping-lemma]

が通常の言語である場合、その言語のすべての文字列に対して、 の長さが よりも大きいか等しいようなL定数n( に依存する) が存在し、 3 つの文字列 に分割できます。LwLwnww = xyz

w以上を選択する必要があるのはなぜnですか? ポンピング長とは？

ポンピング補題の定義 (ウィキより)

L を正規言語とする。次に、L のみに依存する整数 p ≥ 1 が存在し、長さが少なくとも p (p は「ポンピング長」[4] と呼ばれる) の L 内のすべての文字列 w は、w = xyz として記述できます (つまり、w は3 つの部分文字列に分割)、次の条件を満たします。

|y| ≧1; |xy| すべての i ≥ 0 に対して ≤ p、xyiz ∈ L

正規表現011をテストしたいとします正規表現mなので、w=xyzを満たす少なくとも長さpの文字列wがあります

このオートマトンの数は 3 で、p は >= 3 である必要があります しかし、このオートマトンを受け入れる文字列は 011 だけです。|y|を満たすことができません ≧1; |xy| すべての i ≥ 0 に対して ≤ p、xyiz ∈ L

011しか受け付けないのでどうやって搾乳すればいいの？どこが間違っていますか

CSコースでは、次の例があります{a^n | n >= 0}。{a^p | p = prime number}

それらの言語は規則的ですか？ポンピング補題の矛盾を作れる人はいますか?

フィボナッチ文字列は次のように定義されます: k>2 の場合、S1=a、S2=b、および Sk=S k-1S k-2 。たとえば、 S3=ba 、 S4=bab など。フィボナッチ文字列によって生成される言語を L とします。言語「 L 」は規則的ですか? そうでない場合は、Pumping Lemma で反証します。

言語を見ただけでその言語が規則的かどうかを推測するトリックはありますか?

証明方法を選択するには、まず仮説を立てる必要があります。長い問題を解くのにかかる時間を短縮するために必要なヒント/パターンを知っていますか?

たとえば、言語が規則的であり、DFA/文法を構築したくない場合、補題のポンピングに時間を費やさないようにするためです。

例えば：

上記の例を見るだけで、どちらが規則的かを判断する方法は??

わかりました、これはプログラミングの質問ではありませんが、コンピューティングの質問であるため、関連性があります。

基本的に、ポンピング補題を使用して、この言語が正規ではないことを証明するにはどうすればよいですか?

{w in {0,1}* | w の長さが奇数の場合、中央の記号は 0}

計算モデルについては知っていますが、比較的新しいので、できるだけ簡単に答えてください。

事前にどうもありがとうございました！