正規言語(regular lamguage)

言語を構成する最小の要素(アルファベット,ひらがな,カタカナ)である記号集合を $\Sigma$ とし,$\Sigma$ 上の語の全体(スター閉包/クリーネ閉包)を $\Sigma^{*}$ とするとき, $\Sigma$ 上の言語 $\mathcal{L} \subseteq \Sigma^{*}$ が以下を満たすならば,$\mathcal{L}$ は正規言語(regular language)といいます.
すなわち,$\Sigma$ 上の有限オートマトン\[M = (Q,\Sigma,\delta,q_{0},F)\]が存在して,\[\mathcal{L}=\{w \in \Sigma^{*}\ |\ \exists q \in F.q_{0} \xrightarrow{w} q\}\]となること.

オートマトン $M$ が受理する言語 $\mathcal{L}$ を \[\mathcal{L}(M)\]と表します.

要素の数が有限な言語はすべて正規言語となります.

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 セルオートマトン 真偽値の領域 プッシュダウンオートマトン スタック 連接 conjunction