Loading article…
（形式）言語とは、単に文字列の集合のことです。このような集合は、言語に対する演算に基づいた言語方程式によって指定できます。言語方程式は、数値方程式に似た数学的な記述ですが、変数は数値ではなく形式言語の値をとります。2つの言語AとBに対する最も一般的な演算には、集合の和集合A ∪ Bと連結A ⋅ Bがあります。最後に、単一のオペランドを取る演算として、集合A *は言語Aのクリーネスターを表します。
アーデンの規則によれば、集合A * ⋅ Bは、線形方程式X = A ⋅ X ∪ BにおけるXの解となる最小の言語である。ここで、 X、A、Bは文字列の集合である。さらに、集合Aに空語が含まれていない場合、この解は一意である。[ 1 ] [ 2 ]
同様に、集合B ⋅ A *は、 X = X ⋅ A ∪ BにおけるXの解となる最小の言語である。
アーデンの規則は、クリーネのアルゴリズムのように、有限オートマトンを正規表現に変換するのに役立ちます。