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

cs.stackexchange https://cs.stackexchange.com/questions/1031

質問

私たちは正規言語 $\mathrm{REG}$ のクラスについて学びました。正規表現、有限オートマトン、左線形文法のいずれか一つの概念を特徴とするため、その言語が正規であることを示すことが容易です。

では、その逆を示すにはどうすればよいでしょうか?私の TA は、そのためには、すべての正規表現 (またはすべての有限オートマトン、またはすべての左線形文法) について、対象の言語を記述できないことを証明する必要があると主張しました。これは大変な仕事のようですね！

ポンピング補題について読んだことがありますが、とても複雑そうです。

一般的な証明方法や応用例を集めた参考問題を目的としています。見る ここ 文脈自由言語に関する同じ質問に対して。

役に立ちましたか？

解決

矛盾による証明は、言語が規則的ではないことを示すためにしばしば使用されます。$ p $は、すべての通常の言語に当てはまります。特定の言語が$ p $を検証しない場合、それは通常ではありません。次のプロパティを使用できます。

  1. 例示されるように、ポンピング補題 デイブの答え;
  2. 閉鎖プロパティ 通常の言語の（セット操作、連結、クリーンスター、ミラー、同種性）;
  3. 正規言語には、プレフィックス等価クラスの有限数があります。 Myhill – Norede定理.

言語$ l $がクロージャープロパティを使用して定期的ではないことを証明するために、手法は、典型的でないことが知られている言語を取得するために、規則性を維持する操作によって$ l $を通常の言語と組み合わせることです。たとえば、典型的な言語$ i = {a^nb^n | n in mathbb {n} } $。たとえば、$ l = {a^pb^q | p neq q } $。通常の言語は補完の下で閉鎖されているため、$ l $が正規であると仮定します。ここで、$ l^c $と$ a^ star b^ star $の交差点を取ります。これは通常の$ i $を取得します。

Myhill – Nerode定理は、$ i $が規則的ではないことを証明するために使用できます。 $ p geq 0 $、$ i/a^p = {a^{r} b^rb^p | r in mathbb {n} } = i。 {b^p } $。すべてのクラスは異なっており、そのようなクラスの数え切れないほどの無限があります。正規言語には有限数のクラスが必要なので、$ i $は正規ではありません。

他のヒント

Dave の答えに基づいて、ポンピング補題を使用するための段階的な「マニュアル」を次に示します。

ポンピング補題を思い出してください (ウィキペディアから引用した Dave の回答から抜粋):

させて $L$ 常用言語であること。次に、整数が存在します $n\ge 1$ (のみに依存 $L$) すべての文字列が $w$ で $L$ 少なくとも長さの $n$ ($n$ は「ポンピング長」と呼ばれます）は次のように書くことができます $w = xyz$ (つまり、 $w$ は 3 つの部分文字列に分割できます)、次の条件を満たします。

  1. $ | y | ge 1 $
  2. $|xy|\le n$ そして
  3. 「ポンピングされた」 $w$ まだ入っています $L$:すべてのために $i \ge 0$, $xy^iz \in L$.

何らかの言語が与えられていると仮定します。 $L$ そして、ポンピング補題を介してそれが規則的ではないことを示したいとします。証明は次のようになります。

  1. と仮定する $L$ は 通常。
  2. それが規則的である場合、ポンピング補題は、何らかの数が存在することを示します。 $n$ これがポンピング長です。
  3. 選択してください 特定の 言葉 L$ 付き よりも長い長さの $n$. 。難しいのは、どの言葉を採用すべきかを知ることです。
  4. 考慮する 全て 分割する方法 $w$ 3つの部分に分けて、 $w=xyz$, 、 と $|xy|\le n$ そして $y$ 空ではない。のために それぞれ これらの方法のうち、ポンピングできないことを示します。常にいくつかが存在します $i\ge 0$ そのような $xy^iz otin L$.
  5. 結論する：言葉 $w$ (どのように分割しても)「ポンプ」することはできません。 $xyz$) ポンピング補題に矛盾します。つまり、私たちの仮定 (ステップ 1) は間違っています。 $L$ 定期的ではありません。

例に進む前に、ステップ 3 とステップ 4 をもう一度説明します (これが、ほとんどの人が間違える場所です)。ステップ 3 では、特定の単語を 1 つ選択する必要があります。 $L$. 。「00001111」や「」のように、明示的に書き留めます。$a^nb^n$」。例としては、 ない 特定の単語:」$w$」または「接頭辞として 000 が付く単語」。

一方、ステップ 4 では、複数のケースを考慮する必要があります。たとえば、次の場合 $w=000111$ 言うだけでは十分ではありません $x=00、y=01、z=00$, 、そして矛盾に行き着く。こちらも要チェック $x=0、y=0、z=0111$, 、 そして $x=\イプシロン、y=000、z=111$, 、およびその他すべての可能なオプション。

それでは、手順に従って証明してみましょう $L= \{ 0^k1^{2k} \mid k>0 \}$ 定期的ではありません。

  1. 仮定する $L$ 定期的です。
  2. させて $n$ ポンピング補題によって与えられるポンピング長になります。
  3. させて $w = 0^n 1^{2n}$.
    （サニティーチェック： $|w|\gt n$ 必要に応じて。なぜこの言葉が?他の単語も同様に機能します。適切な方法を思いつくにはある程度の経験が必要です $w$）。もう一度注意してください $w$ は特定の単語です: $\underbrace{000\ldots0}_{n ext{ 回}}\underbrace{111\ldots1}_{2n ext{ 回}}$.
  4. それでは、分割するさまざまなケースを検討してみましょう $w$ の中へ $xyz$ と $|xy|\le n$ そして $|y|>0$. 。以来 $|xy|<n$ どんなに別れても $w$, $x$ は 0 だけで構成されます。 $y$. 。仮定してみましょう $|x|=s$ そして $|y|=k$. 。私たちはすべての選択肢を考慮する必要があります、それが可能なすべてです $s,k$ そのような $s\ge 0、k\ge 1$ そして $s+k \le n$. このために $L$ これらすべてのケースの証明は同じですが、一般的には異なる可能性があります。
    取る $i=0$ そして検討してください $xy^iz = xz$. 。この言葉は入っていない $L$ という形なので $0^{n-k}1^{2n}$ (何があっても $s$ そして $k$ だった）そしてそれ以来 $k \ge 1$, 、この単語は入っていません $L$ そして私たちは矛盾に行き着きます。
  5. したがって、私たちの仮定は間違っており、 $L$ 定期的ではありません。

同じ方針に沿ってポンピング補題の使用方法を説明する YouTube クリップを見つけることができます。 ここ

ウィキペディアから、 通常の言語のポンプ言語 次のとおりです。

$ l $を正規言語とします。次に、整数$ p ge 1 $（$ l $のみに依存）が存在します。 $ w = xyz $（すなわち、$ w $を3つのサブストリングに分割できます）として書かれ、次の条件を満たします。

  1. $ | y | ge 1 $
  2. $ | xy | le p $ and
  3. すべての$ i ge 0 $、$ xy^iz in l $。
    $ y $は、ポンプで汲み上げることができるサブストリングです（除去または繰り返される回数、結果の文字列は常に$ l $です）。

（1）ポンプするループyが少なくとも1つの長さでなければならないことを意味します。 （2）ループが最初のp文字内で発生する必要があることを意味します。 xとzに制限はありません。

簡単に言えば、通常の言語lについては、十分に長い単語$ w in l $を3つの部分に分割できます。 IE $ w = xyz $。$ k ge 0 $のすべての文字列$ xy^kz $も$ l $です。

今考えてみましょう 例. 。 $ l = {（01）^n2^n mid n ge0 } $とします。

これが規則的ではないことを示すには、すべての分解$ w = xyz $がどのように見えるかを考慮する必要があります。 $（$ 3p $のこの特定の単語を見ることを選択します。ここで、$ p $はポンプの長さです）。文字列の$ y $部分が発生する場所を考慮する必要があります。最初の部分と重複する可能性があるため、$（01）^{k+1} $、$（10）^{k+1} $、$ 1（01）^k $または$ 0（10）^のいずれかに等しくなります。 K $、$ k ge 0 $の場合（$ | y | ge 1 $を忘れないでください）。 2番目の部分と重複する可能性があります。つまり、$ k> 0 $の場合、$ y = 2^k $を意味します。または、単語の2つの部分に重複する可能性があり、フォーム$（01）^{k+1} 2^l $、$（10）^{k+1} 2^l $、$ 1（01（01）があります。 ）^k 2^l $または$ 0（10）^k 2^l $、$ k ge0 $および$ l ge1 $。

次に、それぞれをポンピングして矛盾を得るために、これはあなたの言語ではない言葉になります。たとえば、$ y = 0（10）^k2^l $を取ると、たとえばポンプ補助補助補助紙によると、$ xy^2z = x0（10）^k2^l0（10）^k2^lz $ $ x $と$ z $の適切な選択のために、言語になります。しかし、$ 1 $の前に$ 2 $が表示されるため、この単語は言語に載ることはできません。

他のケースは、$（01）$の数が2ドルの数を超えるか、その逆になるか、または構造$（01）^n2^n $を持たない単語になります。たとえば、2つの$ 0 $のsを連続して持っています。

$ | xy |を忘れないでください le p $。ここでは、証拠を短縮することは役に立ちます。上記の分解の多くは、$ z $部品を長すぎるため、不可能です。

上記の各ケースは、そのような矛盾につながる必要があります。出来上がり！言語は規則的ではありません。

与えられた言語の場合、$ l subseteq sigma^*$、let

$ qquad displaystyle s_l（z）= sum limits_ {n geq 0} | l cap sigma^n | cdot z^n $

（普通） 生成関数 $ l $の、つまり、長さごとにワードカウントのシーケンス。

次のステートメントには[FLSE09, 、p52]：

$ qquad displaystyle l in mathrm {reg} quad longrightarrow quad s_l text {Rational} $

つまり、$ s_l（z）= frac {p（z）} {q（z）} $ $ p、q $ polynomials。

したがって、生成関数がある言語 いいえ 合理的なものは規則的ではありません。残念ながら、すべて 線形言語 また、合理的な生成関数があるので、この方法はより単純な非正規言語では機能しません。もう1つの欠点は、$ s_l $を取得する（合理的ではないことを示す）が難しい場合があることです。

例： 正しくネストされた括弧の言葉を考慮してください。 dyck言語. 。によって生成されます 明確な文法

$ qquad displaystyle s to [s] mid varepsilon $

方程式に変換できます

$ qquad displaystyle s（z）= z^2s^2（z） + 1 $

1つのソリューション（すべての正の係数を持つもの）は

$ qquad displaystyle mathcal {s}（z）= frac {1 - sqrt {1-4z^2}} {2z^2} $。

as $ s_l = mathcal {s} $ [KUIC70]および$ mathcal {s} $は合理的ではなく、dyck言語は規則的ではありません。

  1. 通常の言語の声明の証明は、文法を介して機能し、すぐに線形文法に転送されます（乗算の通勤）。

$ $ [flse09 分析組み合わせ P. Flajolet and R. Sedgewick（2009）
$ $ [kuic70 コンテキストフリー言語のエントロピーについて W. Kuich（1970）

これはここからの私の答えの拡張バージョンです ポンピング補題を使用して言語を証明する$ l = {（01）^m 2^m mid m ge0 } $は規則的ではありません これは参照の質問であるはずです。

それで、あなたはポンピング補題が複雑に見えると思いますか？心配しないで。これは、 @Romualdの答えにも隠されているわずかに異なるテイクアプローチです。 （クイズ：どこ？）

すべての正規言語は、決定論的な有限状態オートマトン（DFA）によって受け入れられていることを覚えておいてください。 DFAは、すべての頂点にアルファベット内の各文字の1つの外線が正確に1つある有限指示グラフです。文字列は、「start」というラベルの付いた頂点に基づいてグラフを散歩させ、DFAはこの歩行が「Accept」というラベルの付いた頂点で終わるかどうかを受け入れます。 （頂点は「状態」と呼ばれます。なぜなら、数学の異なる領域が同じことのために独自の用語を構成することを好むからです。）

この考え方では、それを見るのは簡単です： 文字列$ a $ a $ bと$ b $の場合、DFAを同じ状態に駆動する場合、他の文字列$ c $、$ ac $、$ bc $の場合、DFAを同じ状態に駆動します。 なんで？散歩の指定点とそれを定義する弦が終わりを完全に決定するためです。

少し異なる方法： $ l $が正規で、文字列$ a $ aと$ b $が同じ状態に認識されているオートマトンを駆動する場合、すべての文字列$ c $で、$ ac $と$ bc $のいずれかが$ l $であるか、どちらも$ l $ではありません。

これを使用して、言語が想像していないことを示すことができます。その後、$ a $ aと$ b $を同じ状態に駆動し、$ c $を作成して、$ ac $が言語と$になります。 BC $はそうではありません。 @daveの答えから言語の例を取ります。定期的であると想像してみてください。そのため、$ m $の状態を持つDFAを認識している人がいます。ピジョンホールの原理は、$ {（01）^i：0 le i le m+1 } $のうち少なくとも2つが同じ状態にdfaを送信すると言います。 $ b =（01）^q $。 $ p neq q $であるため、$ a2^p $が言語にあり、$ b2^p $はそうではないことがわかります。そのため、この言語は規則的ではありません。

良いことは、この例は、言語が規則的ではないことを証明するためのテンプレートであるということです。

  • 文字列のファミリー$ {a_i：i in mathbb {n} } $は、それぞれが「テール」$ t_i $を持っているため、$ a_it_i $が言語と$ a_it_j $になります。 $ i neq j $はそうではありません。
  • 上記の逐語上の引数を適用します。 （これは許可されています。これは、ピジョンホールの原則を呼び出すのに十分な$ a_i $が常にあるためです。）

他のトリックはありますが、これは宿題の問題のほとんどに簡単に機能します。

編集： 以前のバージョンは、このアイデアがポンプ補助補助具にどのように関連しているかについて議論しました。

答えに従ってください ここ, 、Kolmogorvの複雑さに基づいて、非規則性を証明する方法について説明します。

このアプローチについては説明します 「コルモゴロフの複雑さによる正式な言語理論への新しいアプローチ」, 、Ming LiとPaul MB Vitanyi（セクション3.1を参照）。

$ k（x）$は、文字列$ x $のコルモゴロフの複雑さを示します。つまり、チューリングマシン$ m $の最短エンコーディングの長さを示します。しましょう）。その後、次の補題を使用して、非規則性を証明できます。

kc-relumentity: ：$ l subseteq sigma^*$を正規言語にすると、$ l $にのみ依存する一定の$ c $が存在します。 $ n'th $ string（辞書順序と比較）$ l_x = left {y in sigma^*| xy in l right } $、$ k（y） le o （ log n）+c $。

$ x in sigma^*$について、上記の補題を次のように理解することができます（そして証明することもできます^*$ $ n'th $ stringを$ l_x $ $を記述する必要があります。

  • $ l $を受け入れるオートマトン
  • プレフィックス$ x $を処理した後のオートマトンの状態
  • インデックス$ n $

$ x $を処理した後、$ x $自体ではなく状態を覚えておく必要があるため、$ l $に応じてこの係数を定数で非表示にすることができます。インデックス$ n $には記述するために$ log n $ビットが必要であり、上記の結果を取得します（完全性のために、$ y $を生成するために必要な特定の指示を追加する必要がありますが、これは最終的な説明に一定の要因を追加するだけです）。

この補題は、一部の正規言語$ l $と$ x in sigma^*$の$ l_x $のメンバーであるすべての文字列のコルモゴロフの複雑さをどのようにバインドするかを示しています。非規則性を示すために、$ l $が規則的であると想定し、境界があまりにも制限的であることを証明できます（例：無限の文字列セットのコルモグロフの複雑さなど）。

上記の答えには、この補題を使用して$ l = left {1^p |を表示する方法の例が含まれています。 text {p is prime} right } $は規則的ではありません。1つの例は論文に記載されています。完全性については、ここで$ l = left {0^n1^n |を証明する方法を示します。 n ge 0 right } $は規則的ではありません。

$ x in left {0,1 right }^*$を与えられた場合、$ y_i^x $で$ l_x $の$ i'th $ $ $を示します。 $ y_1^{0^i} = 1^i $であることに注意してください。上記の補題を使用して、フォーム$ x = 0^i $のプレフィックス$ x $に焦点を当て、$ n = 1 $を修正すると、$ forall i ge 0：k（y_1^{0^i}）を取得しますle c $。 $ y_1^{0^i} = 1^i $であるため、これは、フォームのすべての文字列のコルモゴロフの複雑さを定数で$ 1^i $によって結合できることを意味します。これは明らかに偽です。 $ x $、例えば$ x = 0^n $を単一の$ x $、$ k（0^n） ge log n $を満たす十分な大きさの$ n $について調べることができたことに言及する価値があります（高で始めることができます複雑さのプレフィックス）。 $ y_1^x = 1^n $であるため、$ k（1^n）を取得しますu003Cc$, contradiction (suppose $n>2^c $）。

単位言語（サイズ1のアルファベットを介した言語）の場合、単純な基準があります。アルファベット$ { sigma } $を修正し、$ a subseteq mathbb {n} $の場合、$$ l（a）= { sigma^n：n in a }を定義します。 $$

定理。 $ a subseteq mathbb {n} $とします。以下は同等です。

  1. $ l（a）$は通常です。

  2. $ l（a）$はコンテキストフリーです。

  3. $ n_0、m geq 1 $が存在するため、すべての$ n geq n_0 $について、$ n in a $ iff $ n+m in a $を保持します。 （$ a $はそうだと言います 最終的には周期的です.)

  4. $ a_i = 1_ {i in a} $とします。その後、$ 0.a_0a_1a_2 ldots $は合理的です。

  5. 生成関数$ sum_ {i in a} x^i $は合理的な関数です。

定理は多くの点で証明できます。たとえば、ポンピング補題、myhill – hernode理論、パリクの定理、単一言語のDFAの構造を使用します（ポラードの$ rho $のように、「$ rho $」のように見えますアルゴリズム）など。これが有用な結果です。

結果。 $ a subseteq mathbb {n} $を、$ l（a）$が正規であると仮定します。

  1. Limit $ rho = lim_ {n to infty} frac {| a cap {1、 ldots、n } |} {n} $が存在します。 （これは 漸近密度 $ a $。）

  2. $ rho = 0 $の場合、$ a $が有限です。

  3. $ rho = 1 $の場合、$ a $がcofinite（つまり、$ overline {a} $が有限です）。

例として、言語$ l（ {2^n：n geq 0 }）$は規則的ではありません。セットには漸近密度が消えるが、無限であるためです。

通常の言語のクラスは、組合、交差、補完、同型性、定期的な代替、逆同性愛など、さまざまな閉鎖操作の下で閉鎖されています。これは、特定の言語が非正規であることがすでに知られている言語を削減することによって規則的ではないことを証明するために使用できます。

非常に簡単な例として、言語が知っていると仮定します $ {a^nb^n：n geq 0 } $ 定期的ではありません。その後、言語を証明することができます $ {w in {a、b }^*： ＃_ a（w）= ＃_ b（w）} $ （同様に多くのすべての単語の言語 $ a $砂 $ b $s）次のように規則的ではありません：

仮定 $ l = {w in {a、b }^*： ＃_ a（w）= ＃_ b（w）} $ 定期的でした。それで $ l cap a^*b^*$ また、定期的です。だが $ l cap a^* b^* = {a^nb^n：n geq 0 } $, 、定期的ではないことが知られています。

これがより複雑な例です。言語を示しましょう $ l '= {（0+1）^n2（0+1）^n：n geq 0 } $ 定期的ではありません。

させて $ h $ によって与えられた同性愛マッピングになります $ h（0）= 0 $, $ h（1）= 1 $, $ h（2）= epsilon $. 。もしも $ l '$ 次の言語も次のようになりました。 $ h（l ' cap 0^*21^*）= {0^n 1^n：n geq 0 } $. 。ただし、後者は規則的ではないことを知っています。

最後に、ここに逆の同性愛を使用した例があります。言語を示しましょう $ l '' = {0^n10^n：n geq 0 } $ 定期的ではありません。

させて $ k $ によって与えられた同性愛である $ k（0）= 0 $, $ k（1）= 0 $, $ k（2）= 1 $. 。もしも $ l '' $ 当時は定期的でした $ k^{-1}（l ''）$ しかし、それは単なる言語です $ l '$ 前の例から。

Myhill – Nerode Theoryを使用してください。

させて $ l $ 言語になります。私たちはその2つの言葉を言います $ x、y $ それは 同等 モジュロ $ l $ （または： $ l $）単語が存在する場合 $ z $ そのようなものです $ xz、yz $ 入っています $ l $. 。任意のDFAで $ l $, $ delta（q_0、x） neq delta（q_0、y）$ （エクササイズ）。これは、次の基準を意味します。

させて $ l $ 言語になります。ペアワイズの比類のない単語の無限のセットが存在すると仮定します（つまり、無限のセットがあります $ s $ そのようなものは2つの非等です $ x、y in s $ 同等のモジュロです $ l $）。それで $ l $ 定期的ではありません。

この基準を適用する簡単な例は次のとおりです。

言語 $ l = {a^nb^n：n geq 0 } $ 定期的ではありません。

証拠。 させて $ s = {a^n：n geq 0 } $. 。 2つの異なる単語があると主張しています $ s $ 同等のモジュロです $ l $. 。確かに、させてください $ a^i、a^j in s $, 、 どこ $ i ne j $. 。それで $ a^ib^i in l $ しかし $ a^ib^j notin l $.

この方法の重要な特徴は、成功することが保証されていることです。 $ l $ 定期的ではない場合、ペアワイズの初めての単語の無限のセットが存在します。これはの結果です Myhill – Norede定理. 。簡単に言えば、同等のモジュロ $ l $ （等価モジュロの否定 $ l $ 上記で定義）は同等の関係であり、言語です $ l $ 等価モジュロの等価クラスの数が通常の場合です $ l $ 有限です。もしも $ l $ 定期的ではありません。各等価クラスから1つの単語を取り出すと、無限の単語のセットが構成されます。

言語が与えられます $ l $, 、すべての文字列に対して $ x $ 文字列のセットがあります $ y $ そのような $ xy in l $. 。そのような各セットは、状態マシンの状態として使用できます。

あなたがする必要があるのは、そのようなセットの数が有限ではないことを示すことです。

例として、 $ l = {a^nb^n：n≥0} $. 。与えられた $ x = a^nb $ いくつかのための $n≥1$, 、唯一の文字列 $ y $ そのような $ xy in l $ は $ y = b^{n-1} $. 。だからすべてのために $ n $ 別のセットがあります。つまり、意味します $ l $ 定期的ではありません。

したがって、一般的に、文字列の無限のセットを見つけた場合 $ x $ それぞれのように $ x $ 別のセットを与えます $ {y：xy in l } $ その場合、言語は有限状態マシンによって認識されることはできず、したがって定期的ではありません。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top