正規表現
[math] \newcommand{\mathsetextension}[1]{% \left\{ #1 \right\}% } \newcommand{\mathsetintension}[2]{% \left\{ #1 \left| #2 \right.\right\}% } \newcommand{\mathof}[2]{% \mathop{#1}\left(#2\right)% } \newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}} \newcommand{\mathgen}{\rightsquigarrow} \newcommand{\mathgenfun}[1]{\mathbf{#1}} \newcommand{\mirrorim}[1]{\overleftarrow{#1}} \newcommand{\emptyword}{\varepsilon} \newcommand{\kleenecl}[1]{{#1}^{*}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\qed}{\blacksquare} [/math]
正規表現（regular expression）とは正規言語の表現方法である。
以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。
正規表現の定義
この節では正規表現およびそれに対応する形式言語を定義する。
定義 1 (正規表現)
記号集合 $\Sigma$ 上の正規表現とは次のように帰納的に定義される。
- 空集合を表す記号 $\emptyset$ は正規表現である。
- 空列を表す記号 $\emptyword$ は正規表現である。
- $a\in \Sigma$ のとき、記号列 $a$ は正規表現である。
- $\alpha$, $\beta$ が正規表現であるとき、$(\alpha\beta)$ は正規表現である。
- $\alpha$, $\beta$ が正規表現であるとき、$(\alpha + \beta)$ は正規表現である。
- $\alpha$ が正規表現であるとき、$\kleenecl{(\alpha)}$ は正規表現である。
定義 2 (正規表現に対応する形式言語)
記号集合 $\Sigma$ 上の正規表現 $\alpha$ に対応する形式言語 $\interpret{\alpha}$ は次のように帰納的に定義される。
- $\interpret{\emptyset}=\emptyset$
- $\interpret{\emptyword}=\{\emptyword\}$
- $a\in \Sigma$ について $\interpret{a}=\{ a \}$
- $\interpret{(\alpha\beta)}=\interpret{\alpha} \cdot \interpret{\beta}$ (ただし、$\cdot$ は 連接を表す)
- $\interpret{(\alpha + \beta)}=\interpret{\alpha}\cup\interpret{\beta}$
- $\interpret{\kleenecl{(\alpha)}}=\kleenecl{ \interpret{\alpha} }$ (ただし、$\kleenecl{\text{-}}$ は Kleene閉包を表す)
正規表現の略記
$\interpret{(\alpha\beta)\gamma}=(\interpret{\alpha} \cdot \interpret{\beta})\cdot \interpret{\gamma}=\interpret{\alpha} \cdot (\interpret{\beta}\cdot \interpret{\gamma})=\interpret{\alpha(\beta\gamma)}$ であるから、 $(\alpha\beta)\gamma$ と $\alpha(\beta\gamma)$ を特に区別する必要はない。 以降、$\alpha\beta\gamma$ を正規表現$(\alpha\beta)\gamma$ または $\alpha(\beta\gamma)$ の略記とする。
同様の理由で、$\alpha + \beta + \gamma$ を正規表現$(\alpha + \beta) + \gamma$ または $\alpha + (\beta + \gamma)$ の略記とする。
また、これ以降一番外側の括弧についても適時省略することにする。
正規表現の例
この節では正規表現の例を紹介する。
例 3 ($0$ と $1$ からなる有限記号列全体)
$\kleenecl{(0+1)}$ は $0$ と $1$ からなる有限記号列全体を表す正規表現である。
例 4 ($0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列全体)
$\kleenecl{(0)}1\kleenecl{(0)}1\kleenecl{(0)}1\kleenecl{(0)}$ は $0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列全体を表す正規表現である。
例 5 (自然数の二進表現全体)
$(0+1\kleenecl{(1+0)})$ は自然数の二進表現全体を表す正規表現である。
正規言語、有限オートマトンとの関係
この節では正規表現と正規言語、有限オートマトンの関係を述べる。
定理 6
言語 $L$ について以下は同値である．
- $L$ は正規言語である。
- $L=\interpret{\alpha}$ なる正規表現 $\alpha$ が存在する。
- $L$ を受理する有限オートマトンが存在する。
この定理の証明は、項目 正規言語を参照せよ。
参考文献
- 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
- 五十嵐喜英他、『数理情報科学シリーズ ２４ オートマトンと形式言語の基礎』、牧野書店、2011
関連項目
| 文法のタイプ | 言語のクラス | 計算モデル |
|---|---|---|
| タイプ0 | 句構造言語 | Turingマシン |
| タイプ1 | 文脈依存言語 | 線形有界オートマトン |
| タイプ2 | 文脈自由言語 | プッシュダウン・オートマトン |
| タイプ3 | 正規言語 | 有限オートマトン |
