dfa - この言語が規則的かどうかを証明するにはどうすればよいですか?

Question

この言語が規則的かどうかを証明するにはどうすればよいですか?

L = {a ⁿ b ⁿ : n≥1} 和集合 {a ⁿ b ⁿ⁺² : n≥1}

Answer 1

アプローチと証明のスケッチを示します。穴がいくつかあるので、自分で埋めることができると思います。

アイデアは、nerode の定理を使用することです。つまり、 R _Lの同値群が無数にあることを示し、定理から、言語が不規則であることが導き出されます。

2 種類のセットを定義します。

1. G_j = {a ⁿ b ^k | [-2,-1,0,1,...] の各 j に対して nk = j , k≥1}
2. [0,1,...] の各 j に対してH_j = {a ^{j }}
3. G_illegal = {0,1} ^* / (G_j U H_j) [指定された範囲内の各 j に対して]

xfor each inG_illegalと for each zin {a,b} ^* :xzが in でないことは簡単にわかりLます。

したがって、 for every x,y inG_illegalおよび for each zin {a,b} ^* : xzin L<-> yzin L.

また、 for each zin {a,b} ^* - and for each x,y一部のG_j[j両方で同じ]:

• を含む場合、との両方がz含まれていないaxzyzL
• z= b ^jの場合、xz = a ⁿ b ^k b ^jであり、k+j = n-xzが in であるためLです。yにも同じことyzが当てはまりますL。
• z= b ^j+2の場合、 xz = a ⁿ b ^k b ^j+2であり、k+j+2 = n+2-xzが in であるためLです。yにも同じことyzが当てはまりますL。
• それ以外の場合、i≠j かつ i≠j+2 でxある b ⁱxzであり、との両方yzが にないことがわかりますL。

したがって、すべての j およびすべてx,yの inG_jおよび for each zin {a,b} ^* : xzin L<-> yzin L.

H_j同じアプローチを使用して、すべてについて同じことを証明します。

また、各xG_j U H_j について、および G_illegal のそれぞれyについて - z= b ^jの場合、xz は L にあり、yz は L にない ことを示すのは簡単です。G_j の
場合x、およびyH_i の場合、z = ab ^j+の場合1 - 入ってxzいないものが見やすい。 for 、G_j および G_i ではそれぞれ、または、H_j では、H_i - for = b ^j :が含まれている一方で、含まれていないことが簡単にわかります。LyzL
xyxyzxzLyz

作成した集合が、実際にはnerode の定理からR _Lの同値関係であることを証明したところです。これらの集合は無限にあるため、それぞれが R _Lの同値関係です[we has and every ] -から導出できます。言語が不規則であるという nerode の定理。H_jG_jjL

Answer 2

通常の言語にはポンピング補題を使用できます。基本的に、与えられた整数 n の文字列と、この文字列の xyz への分割が |xy| <= n、および |y| > 0 の場合、文字列の y 部分をポンピングできますが、それは言語にとどまる必要があります。つまり、xy^iz が一部の i の言語にない場合、その言語は規則的ではありません。

証明は次のようになります。一種の敵対証明です。この言語は規則的だと誰かが言ったとします。次に、n > 0 の数を求めます。長さが n より大きい便利な文字列を作成し、敵に渡します。|xy| である限り、任意の方法で文字列を x、yz に分割します <= n。次に、同じ言語ではない文字列が見つかるまで、y をポンピングする (i 回繰り返す) 必要があります。

この場合、私はあなたに言います：私にnをください。n を修正します。私はあなたに言います：文字列「a^nb^{n+2}」を取り、それを分割するように言います。この文字列をどのような方法で分割しても、|xy| を作成する必要があるため、k > 0 で常に y = a^k を作成する必要があります。<= n で、私の文字列は a^n で始まります。これがトリックです。敵がそれを分割できるように、敵にひもを与えます。敵は、あなたがポンプできる部分をあなたに与えます。ここで、y を 0 回ポンプすると、m < n で "a^mb^{n+2}" が得られますが、これはあなたの言語にはありません。終わり。1 回、n 回、n 回ポンピングすることもできます。階乗時間、言語を残すために必要なもの。

この定理の証明は、通常の言語がある場合、固定された n に対して n 個の状態を持つオートマトンがあることを示しています。文字列が n 文字を超える場合、オートマトンで何らかのサイクルを経る必要があります。サイクルに入る前の文字列の部分を x 、サイクルの部分を y とすると、必要な回数だけサイクルを実行し続けることができるため、y を必要なだけポンプでくみ上げることができることは明らかです。 、そして結果の文字列はその言語である必要があります。これは、そのオートマトンによって認識されるためです。定理を使用して非正則性を証明するには、想定されるオートマトンがどのようになるかわからないため、n とオートマトン内のサイクルの位置の選択を敵に任せる必要があります (オートマトンですが、敵に次のように言います。