2

YouTube で Coderisland の有限状態マシン、DFA、および NFA に関する講義を見てきました。あるディスカッションで、彼はポンピング補題を使用して言語が規則的でないことを示す方法について話しています。レンマを適用する方法がよくわからないので、正しく行っているかどうかを理解したい. 私が次のようなものを持っていたら：

w = {a n b k , n =/= k}

私は次のように言うことができるという点で正しいですか：

h = {a n b n + r , r > 0} はwのサブセットであるため、 hが正則でないことを補題によって示すと、hはwのサブセットであるため、 wは正則であってはなりません。

これを示す方法は次のとおりです。

  1. h = xyz
  2. |xy| <= n
  3. x = n-r
  4. y = a r
  5. z = b n + r
  6. xyz = a n-r a r b n + r
  7. xy 2 z = a n-r a 2r b n + r = a n + r b n + r

したがって、a n + r b n + rは {a n b n + r , r > 0} の形式ではないため、hは規則的ではありません。また、 hは規則的ではないため、 hは次の要素であるため、 wは規則的であってはなりません。w。

私はそれを正しく適用しましたか？{a n b n }のような簡単な言語に適用する方法は理解できます。なぜなら、この補題をこの言語に直接適用できるからです。 、それに補題を適用します。

私がそれを正しく適用していない場合、私の言語が規則的 (または規則的) ではないこと、別のレンマを使用すること、またはクロージャー プロパティを使用することを示す方法はありますか?

これは本当に素晴らしいトピックです。ポンピングの補題を完全には理解していなくても、さらに詳しく調べることに興奮しています!

4

1 に答える 1

1

あなたの証明には 2 つの間違いがあります。

まず、あなたのこの発言の誤りは次のとおりです。

hが正則でないことを補題によって示すと、hはwのサブセットであるため、 wは正則であってはなりません。

言語L = {a n b m | n,m 自然数} hはLのサブセットですが、正規表現 a*b* で表すことができるため、明らかにLは正則です。

しかし、実際にはhを考慮する必要がない解に非常に近づいています。代わりにw内の文字列を選択して、どのように Pumping Lemma を適用しても、wにない文字列が常に得られるようにする必要があります。

これは、ポンピング補題のステップ 3 での 2 番目の間違いです。ポンピング補題では、「その文字列にポンピング補題を適用すると、常に言語の外にある文字列が得られるような、その言語の要素がある」ことを証明する必要があります。

あなたの証明では、なぜそうでなければならないのかを説明せずに、意図的に x = a n-rを選択します。たとえば、実際には x = a n-2である場合があります。この場合、幸いなことに、xy r+1 z を考慮すると、間違いなく b よりも多くの a が存在するため、ポンピング補題を満たさない (したがって正則ではない) という同じ結論が得られます。

問題を証明する正しい方法の 1 つは、ポンピング補題を直接適用することです (補数を使用したり、正規言語と交差させて交差が正規ではないことを証明したりするなどの方法があります) が、ポンピング補題を説明する目的で、この言語にポンピング補題を適用する方法を紹介します。

したがって、問題はw = {a n b k , n=/=k} であり、それが規則的ではないことを証明する必要があると述べています。

  1. ここで、文字列 s = a n b n!+n (つまり、n 個の a の後に n 個の階乗と n 個の b が続く) を考えます。補題をポンピングすることにより、wが正則である場合、s = xyz であり、|xy|<=n であるような xyz が存在するはずです。

  2. |xy|<=n であり、s の先頭にnがあるため、x と y の両方に a のみが含まれている必要があります。y = a m とします。1<=m<=n であることがわかっています。

  3. これで、a と b の数の差は (n!+n)-n = n! になりました。この数は、1 から n までの範囲の任意の数で割り切れます。したがって、n!/m は整数です。q = n!/m とします。

  4. 文字列 xy q+1 z を考慮すると、a の数は (nm)+(q+1)*m = n-m+qm+m = n+qm = n+n! となります。これは次と同じです。 bの数。したがって、xy q+1 z は言語wにはありません。なぜなら、a の数は b の数と同じだからです。したがって、言語wはポンピング補題を満たさない。

  5. したがって、 wは正則ではありません。

コメントの質問に対処するには、補数を使用して証明します。

  1. wが正則であるとします。その場合、補数w'も正則でなければなりません。

  2. しかし、補数w' = {a n b n , n 自然数} は正則ではありません (既に示しましたよね?)。

  3. したがって、 wは正則ではありません。

于 2014-01-26T11:41:13.293 に答える