🦎クリーネの正規集合

あたり総研


クリーネの正規集合は、コンピュータサイエンスにおいて、有限オートマトン（FA）、正規表現（RE）、および正規文法（RG）によって記述される集合のことです。
これらの概念は、いずれもコンピュータサイエンスの基本的な概念で、特に計算理論や自然言語処理の分野で重要です。

  1. 有限オートマトン (FA): これは、状態と、状態間を移動するトランジション（遷移）から成る数学的なモデルです。FAは、入力された文字列が特定の条件を満たすかどうかを判断するのに使われます。

  2. 正規表現 (RE): 正規表現は、文字列の集合を表現するための表現法です。正規表現は、検索エンジン、テキストエディタ、プログラム言語のコンパイラなど、多くのアプリケーションで利用されています。

  3. 正規文法 (RG): 正規文法は、生成規則の集合から成る形式文法です。これは、特定の文字列の集合を生成するのに使われます。

これら三つの概念は、互いに等価であり、ある正規集合は、有限オートマトン、正規表現、正規文法のいずれでも表現することができます。
たとえば、{a^n b^n | n ≥ 0} という集合は、n 個の a の後に n 個の b が続く文字列の集合を表します（例: "", "ab", "aabb", "aaabbb", ...）。この集合は、正規集合ではないため、有限オートマトン、正規表現、正規文法のいずれでも表現することはできません。
逆に、 {0, 1}* という集合は、0と1から成る任意の文字列の集合を表します（例: "", "0", "1", "01", "10", "001", "111", ...）。この集合は、正規集合であり、有限オートマトン、正規表現、正規文法のいずれでも表現することができます。


お願い致します