それを証明する直接的な方法があります:pがポンピング長であり、 string を使用する場合、分解が何であれ、言語にない文字列は等しくなります。s = 0p1p+p!s = xyzxy1+p!/|y|z0p+p!1p+p!
ここで与えられた y の値がわかりません。
2716 次
1 に答える
0
y"ポンピング" (* 回繰り返し) できる部分文字列であり、それでも言語を規則的に保つことができます。基本的に、どこかにループを見つける必要があり、そのループがそれをy表しています。
基本的に、言語が( 0 の後に1 が続く) 形式である場合、そこにループが存在することはありません。0m1m!mm!
この場合、yは「サブセット言語の仮想ポンプ文字列」を表します- 存在できないため、仮想です! 明らかに、この小さな言語をポンピングすることはできません。繰り返すとすぐに言語から抜け出すからです。(例を考えてみましょう - これに対するポンプ文字列を見つけることができますか?) したがって、規則的ではない言語の特殊なケースがあり、そのため言語は一般的に規則的ではありません。(確かに通常の特殊なケースが含まれていますが、これは論争の的ではありません){0m1m!}00111111
于 2014-10-16T02:30:01.590 に答える