問題タブ [pumping-lemma]

1. 正規言語のポンピング補題を使用して、

   言語 L = { a ⁱ , b ^j c ^k | i、j、k は非負の整数で、i=j または i=k }

規則的ではない

2. 上記の言語の CFG を設計する

これが私が思いついたものです

今、私は問題を抱えているチョムスキー正規形に上記のCFGを変換する必要があります...助けはありますか?

それを証明する直接的な方法があります:pがポンピング長であり、 string を使用する場合、分解が何であれ、言語にない文字列は等しくなります。s = 0p1p+p!s = xyzxy1+p!/|y|z0p+p!1p+p!

ここで与えられた y の値がわかりません。

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

言語 {a^2^n | n >= 0}

最初にいくつかの k が選択され、次に vx != イプシロンおよび #(vwx) <= k となるように z = uvwxy が選択されることは理解していますが、この言語が文脈自由ではないことを証明する i は考えられません。

私の質問は、正規言語のポンピング補題を使用して、有限言語の最長文字列がその言語を認識する DFA の状態数よりも少なくなければならないことを証明することに関するものです。これについて代数的な議論を見つけたいと思っていましたが、その証明はピジョンホールの原理に頼らなければならないようです。p = 有限言語を認識する DFA 内の状態の数である場合、ピジョンホールの原則により、最長の文字列は p-1 に等しいサイズでなければなりません (つまり、すべてのピジョンホールにはピジョンが含まれている必要があります。文字列は有限であるため、複数の鳩がいる鳩の巣は存在しません)。

有限言語の最長文字列の長さが p-1 未満の場合、最長文字列が受け入れ状態に到達する保証はありません。長さが p-1 より大きい場合、文字列が完全に処理される前に計算が「終了」する必要があるため、DFA によって受け入れられません。

上記は、有限言語の最長の文字列の長さが状態の数以下でなければならないことを証明するための有効な引数ですか?