12

この問題の解決/証明に問題があります。何かアイデアはありますか？

4

1 に答える 1

16

L = {a n b m | n > m} は 正規表現ではありません。

はい、問題は最初の数回はトリッキーであり、投票に値します。

Pumping Lemma a required property of regular language は、言語が正規言語ではないことを正式に証明するためのツールです。

正式な定義:正規言語のポンピング補題

Lを正規言語とする。次に、 Lのみに依存する整数p ≥ 1 が存在し、長さが少なくともp ( pは「ポンピング長」と呼ばれます) のL内のすべての文字列wは、 w = xyzと記述できます(つまり、wは 3 つに分割できます)。サブ文字列)、次の条件を満たします。

  1. | | y | 1以上
  2. | | xy | ≤p _
  3. すべての i ≥ 0 に対して、xy i z ∈ L

文字列W = a n b mを選択した場合、(n + m) ≥ pとn > m + 1. Wの選択は有効ですが、この選択では言語が正規言語ではないことを示すことができません。これにより、 (for i =0 and i > 1)のすべての値に対して繰り返すことにより、言語で新しい文字列をポンピングする少なくとも1つの選択肢が常にあるためです。 Wy=aai

言語が規則的でないことを証明するソリューションを書く前に。以下の点をご理解いただき、注意してください:上記のポンピング補題の正式な定義を太字every string wにしました。all i

  • languageで十分に大きなWを使用すると、 Language で新しい文字列を生成できますが、WITH ALL ではできません。Wには多くの可能な選択肢があり(以下の私の証明)、すべての i >=0に対して language で新しい文字列を生成するためのyの選択肢を見つけることができません。したがって、十分に大きなWは言語で新しい文字列を生成できないため、言語は規則的ではありません。

読む：ポンピング補題の正式な定義が言うこと

証明: ポンピング補題を使用

ステップ (1):と の文字列W = a n b mを選択(n + m) ≥ pしますn = m + 1。

Is this choice of W is valid according to pumping lemma?

はい、そのようなWは言語にあるため、 number of a= n > number of b=m です。Wは言語であり、十分に大きい >=pです。

ステップ (2):すべてのy新しい文字列を生成するためにa を選択しました。 i >= 0

そして、今回は選択肢がありません！yなんで？

まず、パターンから新しい文字列を生成するか、結果の文字列の合計数がシンボルの合計数よりも多くなるため、 ybにシンボルを含めることはできないことを理解するのがエッセイです。 ba

第 2に、 y = 一部のaを選択することはできません。これを使用すると、s の数が言語では不可能な number sよりも少ないi=0新しい文字列が得られるためです。そのため、結果の文字列 N(a)=N(b) の a 手段を削除することは、 n>m であるため受け入れられません)abab

したがって、十分に大きい W を見つけることができますが、それを使用すると、正規言語のポンピング レンマ プロパティと矛盾する言語で新しい文字列を生成できません。n > m} は正規の言語ではありません。

于 2013-03-03T10:33:53.660 に答える