正規表現 regular expression

正規表現(regular expression)とは,有限オートマトン受理する言語 $\mathcal{L}$ を表す表現形式です.

正規表現の定義

記号集合 $\Sigma$ 上の正規表現は以下のより定義されます.

上記に以下の2つを加えたものも正規表現と言われます.

言語 $R(p)$

正規表現 $p$ が与えられたとき,言語 $R(p)$ を帰納的に定義することが出来ます.

クリーネ(Kleene)の定理

アルファベットを $\Sigma$ としたとき, 言語 $\mathcal{L} \subseteq \Sigma^{*}$ が正規であるための必要十分条件は,$\Sigma$ 上の正規表現 $p$ が存在していて,\[\mathcal{L} = R(p)\]となることです.

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 非決定性有限オートマトン NFA 状態遷移関数 有限オートマトンの種類 剰余の定理(Remainder theorem)