有限言語とは、有限数の単語を含む言語です。最も単純なケースは、単語をまったく含まないもの、空の文字列、および単一の記号で構成される単一の文字列です (例:a
あなたの例)。
あなたの混乱は、あなたが引用したルールを読み違えたことが原因だと思います(質問にコメントしている人のように)。
(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。
この文章は、言語ですべての文字列を作成するために必要な文字列に対する操作の数についてではなく、定義されている言語を定義するために必要な、より単純な言語に対する操作の数について語っています。あなたが言及した言語は、有限言語(セット{"a"})から始めて、繰り返し演算子を1回適用することによって構築されています。
別の、あまり直接的ではない言い方は、言語や言語に対する操作ではなく、言語を表す式やそれらを組み合わせたより複雑な式にアピールします。オペレーターの数は有限です。
a
"a" という単語だけを含む有限言語を表す のような式を考えてみましょう。その式に単一の繰り返し演算子を追加するとa*
、最初の言語からのゼロ個以上の単語のすべての連結を含む無限言語が得られます。有限言語を表す式から始めて、1 つまたは 2 つの小さな式FとGをパターンE = F | G、E = FG、またはE = F* は通常の言語を表します。有限言語 (有限数の単語を持つ言語) を表す式は、ルールが式で記述されている場合の基本ケースです。有限言語は、ルールが表現の土地に迂回することなく、言語の観点から直接述べられている場合の基本的なケースです。
結合、連結、および繰り返しを無限に何度も適用できるようにする場合 (または、正規表現の規則を使用して無限の式を許可する場合と同等)、結果の言語が正規であるとは限りません。これは、van Wijngaarden 文法で説明されているように、無限大の文脈自由文法が非文脈自由言語を定義できるという観測の正規言語レベルでの類似物です。