Pumping補題の 'pumping length'は正確に何ですか？

Question

私はPumping補題のあらゆるアプリケーションで使用されるこの「魔法の」数字「n」が何であるかを理解しようとしています。テーマに関する研究の時間後、私は、次のWebサイトに来た：それは

nは文字列がループをせずにすることができ、最長 で述べhttp://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf

。最大のnは であることができますが、特定の言語では小さくなることもあります。

言語Lがあるとわかっているから、Lのポンピング長は、Lを認識する有限状態オートマトンの状態量です。これは本当ですか？

最後の行が「特定の言語ではより小さくなる可能性はありますが」と正確に何が言えるでしょうか？私の頭の中で完全な混乱。誰かがそれをクリアすることができますか？

Answer 1

州は言語を認識しません。 DFAは、言語内の単語のセットを正確に受け入れ、他のものは受け入れずに言語を認識します。 DFAには多くの州があります。

通常の言語Lがあり、これはPumping Lemmaによってモデル化することができますが、プロパティnを持ちます。

s状態のDFAの場合、Lを受け入れるには、> = nでなければなりません。

最後の行には、sがnよりも大きく、いくつかの言語が存在すると記載されています。

これは、おそらくhttps://cstheory.stackexchange.com/またはhttps://cs.stackexchange.com/（どちらも自分の価値がわかりません）に適しています。

注：：十分な州のすべてのDFAがその言語を受け入れるわけではありません。また、言語がポンピング補助詞を渡すということは、それが規則的であるということを意味するものではありません（しかし、それが間違っているということは間違いありません）。

FAとDFAの言語が変更されていることに注意してください。これは少し緩いですが、NDFAsはDFAと同じパワーを持ちDFAは書きや​​すく理解しやすいため、DFAが使用されます。

編集通常の言語の例を示しますので、u、v、w、z、nのアイデアを見ることができます。それからsについて議論します。したがって

L = xy^nz, n > 2 (i.e. xyyz, xyyyz, xyyyyz) 
u = xy 
v = y 
w = z 
n = 4 

：

|z| = 3: xyz (i = 0) Not in L, but |z| < n 
|z| = 4: xyyz (i = 1) 
|z| = 5: xyyyz (i = 2) 
etc 

したがって、それはポンピング補題によってモデル化されています。 DFAには少なくとも4つの州が必要です。だから1つ考えよう。

-> State 1: x 

State 1: 
    -> State 2: y 

State 2: 
    -> State 3: y 

State 3: 
    -> State 3: y 
    -> State 4: z 

State 4: 
    Accepting state 
    Terminating state 

期待通りです。この場合、この例はかなりシンプルなので、4つ以上の州でビルドすることはできないと思います（しかし、それが必要なら大丈夫です） 。

Answer 2

届かない状態のFAがある可能性があると思います。FAにはs個の状態がありますが、1個に到達できないため、Lを認識するすべての文字列は（s-1）= n個の状態で構成されるため、n<sです。