が通常の言語である場合、その言語のすべての文字列に対して、 の長さが よりも大きいか等しいようなL定数n( に依存する) が存在し、 3 つの文字列 に分割できます。LwLwnww = xyz
w = length of string. n = Number of States.
w以上を選択する必要があるのはなぜnですか? ポンピング長とは？
質問する
941 次
2 に答える
1
レンマの完全なステートメント ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages ) を見ると、すべての文字列がプレフィックスによって形成されていることを実際に述べていることがわかりますx。回数yと接尾辞z. ここで、最短の場合 (繰り返し部分が 1 回だけ取られる場合) では、 の長さがw言語に必要な状態の数に等しいことは明らかです。このウィキペディアの画像は非常に便利です。
于 2015-03-27T20:06:04.077 に答える
0
あなたは補題（あなたも完全には述べていません）を誤解しているようで、証明の側面とあなたが述べたことを混ぜ合わせています。補題は、すべての通常の languageについて、 に属する少なくともシンボルのすべての文字列が、「ポンピング」できる長さを超えない空でない部分文字列を持ち、常に の別の要素を生成するようなL定数があることを示しています。定数は、(a)「ポンピング長」です。ppLpLp
これは、言語が規則的である場合、それを受け入れる有限状態オートマトンが存在することを観察し、pそのオートマトン内の状態の数を と見なすことによって証明できます (詳細は省略)。
ただし、特定の正規言語を認識する最小の FSA 内の状態の数が、その言語で可能な最小のポンピング長であることを意味するものではありません。たとえば、 { an} と { bn}の結合で構成される言語を考えてみましょうn。この言語を認識するには 4 状態の FSA が必要ですが、最小ポンピング長は 1 です。
于 2015-03-27T20:36:15.350 に答える