正規表現 regular expression

正規表現（regular expression）とは，有限オートマトンが受理する言語 $\mathcal{L}$ を表す表現形式です．

正規表現の定義

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

• $\emptyset$ は，空集合を表す正規表現．
• ${\bf a}$ は，$\Sigma$ の任意の要素 $a \in \Sigma$ のみからなる集合 $\{a\}$ を表す正規表現．
• ${\bf x}$ と ${\bf y}$ が記号列の集合 $X$ と集合 $Y$ を表す正規表現とすると，以下の帰納的導出によって構成される記号列は正規表現．
  • $x|y$ は，集合 $X \cup Y$ を表す正規表現．
  • $xy$ は，集合 $X$ と 集合 $Y$ の連接 $XY$ を表す正規表現．
  • $x^{*}$ は，集合 $X$ のスター閉包 $X^{*}$ を表す正規表現．
• ${\bf \varepsilon}$ は，空記号列のみからなる集合 $\{\varepsilon\}$ を表す正規表現．

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

• $(0-9)$ は，正規表現 $(0|1|2|3|4|5|6|7|8|9)$ と同じ．
• $(a-z)$ は，正規表現 $(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)$ と同じ．

言語 $R(p)$

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

クリーネ（Kleene）の定理

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

Mathematics is the language with which God has written the universe.