有限オートマトンの多様体

有限オートマトンの族 $V$ は以下の条件を満たすときに多様体(variety;代数的多様体)であるといいます.

言語を構成する最小の要素(アルファベット,ひらがな,カタカナ)である記号集合を $\Sigma$ に対して,$V(\Sigma)$ を $V$ に属する $\Sigma$ 上の有限オートマトンの族であるとします.このとき,


註:代数的多様体を variety といい,位相多様体を manifold といいます.有限オートマトンの多様体は代数的多様体です.

1975年に,数学者のアイレンベルグ(1913年9月30日 - 1998年1月30日)は正規言語の組み合わせ的性質,有限モノイドの代数的性質,有限オートマトンの幾何的性質の間の密接な対応関係を公理化した,正規言語の多様体理論を打ち立てました.この理論により,正規表現やオートマトンが正規言語の表現できるように,代数や論理によって正規言語が特徴付けられるということが明らかにされました.
Samuel Eilenberg. Automata, Languages and Machines. Academic Press, Inc., Orland, FL,USA, 1976.

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 正規言語(regular lamguage) セルオートマトン 真偽値の領域 プッシュダウンオートマトン スタック