11

私は計算可能性に関する本でこれを読みました:

(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。

私は「有限言語」に苦労しています。

この言語を考えてみましょう:L = a*

有限ではありません。{0, a, aa, aaa, ...}明らかに無限集合(0=空の文字列)である集合です。

無限の言語ですね。つまり、「無限集合」とは「無限の言語」ということですよね?

明らかにa*正規言語です。そしてそれは無限の言語です。したがって、クリーネの定理により、正規言語になることはできません。矛盾。

よくわかりません。私は「有限言語」が何を意味するのか分からないと思います。

4

5 に答える 5

4

あなたは正しい軌道に乗っています。より明確になる可能性があります。クリーンの定理は、3 つのステートメントの同等性を表現します。

言語は正則です == 言語は正規表現で表現できます == 言語は有限オートマトンで表現できます。

あなたの例は確かに正規言語です。有限言語とは、有限の時間内に一覧表示できる言語であることを期待するものです。

a*彼らが反復について話しているとき、彼らはクリーン スター操作について話している。{empty, a, aa, aaa, aaaa, ...}

編集:

私はこのリンクを見つけました: Kleenes Theoremはかなり役立ちます。「繰り返し」とは、Kleen Star を意味し、元のステートメントは理にかなっています。a*Kleen_Star(a)

于 2013-07-01T20:05:45.630 に答える
3

有限言語とは、有限数の単語を含む言語です。最も単純なケースは、単語をまったく含まないもの、空の文字列、および単一の記号で構成される単一の文字列です (例:aあなたの例)。

あなたの混乱は、あなたが引用したルールを読み違えたことが原因だと思います(質問にコメントしている人のように)。

(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。

この文章は、言語ですべての文字列を作成するために必要な文字列に対する操作の数についてではなく、定義されている言語を定義するために必要な、より単純な言語に対する操作の数について語っています。あなたが言及した言語は、有限言語(セット{"a"})から始めて、繰り返し演算子を1回適用することによって構築されています。

別の、あまり直接的ではない言い方は、言語や言語に対する操作ではなく、言語を表す式やそれらを組み合わせたより複雑な式にアピールします。オペレーターの数は有限です。

a"a" という単語だけを含む有限言語を表す のような式を考えてみましょう。その式に単一の繰り返し演算子を追加するとa*、最初の言語からのゼロ個以上の単語のすべての連結を含む無限言語が得られます。有限言語を表す式から始めて、1 つまたは 2 つの小さな式FGパターンE = F | GE = FG、またはE = F* は通常の言語を表します。有限言語 (有限数の単語を持つ言語) を表す式は、ルールが式で記述されている場合の基本ケースです。有限言語は、ルールが表現の土地に迂回することなく、言語の観点から直接述べられている場合の基本的なケースです。

結合、連結、および繰り返しを無限に何度も適用できるようにする場合 (または、正規表現の規則を使用して無限の式を許可する場合と同等)、結果の言語が正規であるとは限りません。これは、van Wijngaarden 文法で説明されているように、無限大の文脈自由文法が非文脈自由言語を定義できるという観測の正規言語レベルでの類似物です。

于 2015-03-12T02:00:57.560 に答える