0

L={a^n b^m | n=km for k in N}ポンピング補題を使用して、正規言語ではないことをどのように証明すればよいですか?

w私は単語を で、L一部をで取ることから始めました。には 3 つの可能な分解があります。w=a^n b^mn=kmkNw

  1. a^i * a^j * a^(n-i-j) b^m
  2. a^i * a^(n-i) b^j * b^(m-j)
  3. a^n b^i * b^j * b^(m-i-j)

ポイント 2) の中間部分をポンピングすると、混同された単語が生成されますが、これは明らかに にありませんがL、理由がわかりません。

a^j xポンプ回数を考えてみましょう。その場合、新しい単語の a の量は になりますi+xj+n-i-j = n+(x-1)j。私たちn=kmはいくつか知っていmます。x新しい単語が にないようなが存在することを示さなければなりませんL。しかし、仮定してみましょう( の場合を除いて、常に十分な量の a があるj=mため、これは確かに可能ですが、その場合は些細なケースになります)。次に、これはallの形式です。したがって、それぞれについて、for all のような分解があります。したがって、ポンピング補題により、は正則です。n=kmk=0n+(x-1)j = km+(x-1)m = m(n+x-1){a^n b^m | n=km for k in N}xwuvzu v^i zLiL

私は何が欠けていますか？

編集:与えられたポンピング補題の定式化:

L状態を持つ DFA によって受け入れられる通常の言語としますk。長さwの任意の単語とします。次に、 with 、およびin for all のように記述できます。L>= kwu v z|uv| <=kv>0u v^i zLi>=0

4

1 に答える 1

1

これを証明するおそらくより簡単な方法は、最初に言語を変更することです。

正規言語は補数と別の正規表現との交差の下で閉じているためです。

これは、 が正規言語ではないことを証明することで、 が正規言語ではLないことを証明できることを意味します。交差点も同様です。complement(L)L'L

L'が正則でないことも証明するには十分です。

L' = intersection(complement(L),a*b*})

したがって

L'={a^nb^m|n != k*m, for any k in N}

次に、ポンピング補題として使用する部分を示すことができるため、証明がはるかに簡単になります。長さがあればl、倍数に達するのに十分な回数ポンピングできます。

于 2015-01-05T11:47:29.987 に答える