0

計算理論のコースのノートを見直しているのですが、特定の証明を完了する方法を理解するのに苦労しています。質問は次のとおりです。

A = {0^n 1^m 0^n | n>=1, m>=1}  Prove that A is not regular.

これにはポンピング補題を使用する必要があることは明らかです。だから、私たちは持っています

  1. |ヴィ| >= 1
  2. |vxy| <= p (p はポンピング長、>= 1)
  3. uv^ixy^iz はすべての i >= 0 に対して A に存在します

選択する正しい文字列を考えようとすると、これには少し不安が残ります。0^p 1^q 0^p と思っていたのですが、あいまいに aq ができるかどうかわからないし、u に縛りがないので、手に負えなくなるかもしれません..

では、これについてはどうすればよいでしょうか。

4

3 に答える 3

4

CFGに適用されるものではなく、正規言語に適用されるポンピング補題の定義を使用すると、はるかに簡単になります。通常の文字列s=xyzに必要な3つの条件は次のとおりです。

  1. i> = 0ごとに、xy^izはAにあります
  2. | y | > = 0
  3. | xy | <= p

これらの3つの条件を使用して、0 ^ p1 ^ q0^pをもう一度使用してみてください。

ヒント：0 ^ pがあるため、yは0のみで構成されます。したがって、より多くのyを「ポンプイン」すると（xyyzを考慮）、その言語の文字列は取得されません。

于 2010-04-11T17:24:36.413 に答える
3

間違った反復補題を使用しています...ここではAは文脈自由ですが、定期的ではありません。

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

それはあなたが必要とする見出語をあなたに示すはずです...あなたがそれから始めるならば、あなたは答えを思い付くかもしれません。そうでない場合は、お知らせください。回答を編集して、いくつかのヒントを提供します。

于 2010-04-11T17:23:55.923 に答える
0

私は補題なしでそれを解決します: - h(1)=1 h(2)=0 h(0)=0 である h(a) を考えます。あなたの言語に h^-1 を適用し、次に 0^*1^ 2^と交差すると、言語は 0^n1^m2^n になります。- ここで、h'(0)=a、h'(1)=イプシロン、h'(2)=b である h'(a) を使用します。通常ではない a^nb^n が得られます。

なぜこれが簡単なのですか？この基本的なトリックを学べば、この問題を非常に簡単に解決できるからです。

補題について: - A の単語の部分文字列を部分文字列として使用すると、言語が台無しになることが必要になります。私が見ることができる6つのケースがあります（最初から0のみ、最初から0の後に1が続くなど...）

すでに追加されているように、CF-lemma は必要ありません。CFレンマは、言語が通常CFではないことを示すために使用されます。

于 2010-04-11T17:38:42.160 に答える