正規表現
概要
正規表現（regular expression）とは、アルファベット $\Sigma$ 上の言語を、空集合 $\emptyset$・空語 $\varepsilon$・$1$ 記号 $a$ を基礎として、連接 $\alpha\beta$・和 $\alpha+\beta$・Kleene 閉包 $\alpha^{*}$ の三つの演算で帰納的に組み立てて表す式のことである。正規表現 $\alpha$ が表す言語 $L(\alpha)$ は式の構成に沿って定まり、正規表現で表せる言語のクラスは正規言語のクラスと一致する（Kleene の定理）。正規表現から $\varepsilon$ 遷移付き有限オートマトンを組み立てる Thompson の構成と、その逆向きの変換がこの同値の内容であり、文字列検索の実装原理でもある。$\{0^{n}1^{n}\}$ は正規表現では表せない。
前提知識: 形式言語, 有限オートマトン, 帰納的定義, 構造的帰納法
定義
正規表現は、形式言語を「空集合・空語・$1$ 記号の言語から出発し、和・連接・Kleene閉包を有限回施して作る」という手順そのものを式として書いたものである。以下、$\Sigma$ はアルファベット、$\Sigma^{*}$ はその上の文字列全体、$\varepsilon$ は空語を表す。式の中の記号 $\emptyset$、$\varepsilon$、$+$、$*$、括弧は $\Sigma$ の元ではないものとする。
$\Sigma$ 上の正規表現（regular expression）とは、次の規則で帰納的に定められる記号列である。
- $\emptyset$ は正規表現である。
- $\varepsilon$ は正規表現である。
- 各 $a\in\Sigma$ について、$a$ は正規表現である。
- $\alpha,\beta$ が正規表現ならば $(\alpha\beta)$ は正規表現である（連接）。
- $\alpha,\beta$ が正規表現ならば $(\alpha+\beta)$ は正規表現である（和。$\alpha\mid\beta$、$\alpha\cup\beta$ とも書く）。
- $\alpha$ が正規表現ならば $(\alpha)^{*}$ は正規表現である（Kleene 閉包。星ともいう）。
すなわち正規表現全体は、1–3 の記号列を含み 4–6 で閉じた最小の記号列の集合である。
正規表現 $\alpha$ が表す言語 $L(\alpha)\subset\Sigma^{*}$ を、$\alpha$ の構成に関する帰納法で次のように定める。
- $L(\emptyset):=\emptyset$
- $L(\varepsilon):=\{\varepsilon\}$
- $L(a):=\{a\}$（$a\in\Sigma$）
- $L((\alpha\beta)):=L(\alpha)L(\beta)$（言語の連接）
- $L((\alpha+\beta)):=L(\alpha)\cup L(\beta)$（和集合）
- $L((\alpha)^{*}):=L(\alpha)^{*}$（言語の Kleene 閉包）
言語 $L$ に対して $L=L(\alpha)$ となる正規表現 $\alpha$ が存在するとき、$L$ は正規表現で表せるという。$L(\alpha)=L(\beta)$ のとき二つの正規表現は等しい言語を表すといい、$\alpha\equiv\beta$ と書く。
正規表現を読みやすく書くために、次の約束を用いる。
- 演算の優先順位を Kleene 閉包、連接、和の順に高いものとし、この順位から一意に読める括弧は省く。たとえば $ab^{*}+c$ は $((a(b)^{*})+c)$ の略記である。
- 連接と和は表す言語について結合的である（prop-regular-expression-algebraic-laws）ので、$\alpha\beta\gamma$、$\alpha+\beta+\gamma$ と括弧なしに書く。
- $\alpha^{+}:=\alpha\alpha^{*}$（$1$ 回以上の繰り返し）、$\alpha^{?}:=\alpha+\varepsilon$（$0$ 回または $1$ 回）、$\alpha^{n}:=\alpha\alpha\cdots\alpha$（$n$ 個の連接）と略記する。
- $\Sigma=\{a_1,\ldots,a_k\}$ のとき、記号 $\Sigma$ を正規表現 $a_1+\cdots+a_k$ の略記として用いる。したがって $\Sigma^{*}$ は「すべての文字列」を表す正規表現である。
これらの略記は表せる言語の範囲を広げない（略記を展開すれば def-regular-expression の意味での正規表現になる）。
正規表現は記号列（構文）であり、それが表す言語（意味）とは別のものである。$L(\alpha)$ の定義は、正規表現が一意に読めること、すなわち各正規表現が 1–6 のちょうど一つの形を持ち、4–6 の場合の部分式 $\alpha,\beta$ が一意に定まることを用いている。これは括弧をすべて付けた def-regular-expression の形では明らかである（Backus–Naur記法 の記事の注意と同じ事情である）。異なる正規表現が同じ言語を表すことは普通に起こる（ex-regular-expression-equivalent）。
直感
正規表現は「文字列の形」を、有限個の記号と三つの演算（並べる・どちらか・$0$ 回以上繰り返す）だけで書き下す最小限の記法である。原子的な言語 $\emptyset$、$\{\varepsilon\}$、$\{a\}$ から出発し、三つの演算を有限回施して得られる言語がちょうど正規言語である、というのが Kleene の定理（thm-regular-expression-kleene）の内容であり、正規表現は正規言語の「式による記述」、有限オートマトンは「機械による記述」、右線形文法は「生成規則による記述」にあたる。
三つの演算はそれぞれ有限オートマトンの部品の直列接続・並列接続・ループに対応し、正規表現から有限オートマトンを機械的に組み立てられる（prop-regular-expression-to-automaton）。逆に、有限オートマトンの状態を一つずつ消去して残った経路のラベルを式にまとめれば正規表現が得られる（prop-regular-expression-from-automaton）。この往復が、文字列検索の道具としての正規表現の実装原理でもある。
例
以下の例では $\Sigma=\{0,1\}$ とする。
$(0+1)^{*}$ は $\{0,1\}^{*}$ を表す。実際 $L(0+1)=\{0,1\}$ であり、その Kleene 閉包は $0$ と $1$ を $0$ 個以上並べた文字列全体である。同じ言語は $(0^{*}1^{*})^{*}$ や $(1^{*}0^{*})^{*}$ でも表せる。一方 $0^{*}1^{*}$ が表すのは「$0$ の並びの後に $1$ の並びが続く文字列」だけであり、$10\notin L(0^{*}1^{*})$ である。
$0^{*}10^{*}10^{*}10^{*}$ は、$1$ をちょうど $3$ 個含む文字列全体を表す。$1$ の間と両端に $0$ の並び（空でもよい）を置いた形が、そのような文字列の一意な分解になっているからである。$1$ を高々 $3$ 個含む文字列全体は $0^{*}(1+\varepsilon)0^{*}(1+\varepsilon)0^{*}(1+\varepsilon)0^{*}$、$1$ を $3$ 個以上含む文字列全体は $(0+1)^{*}1(0+1)^{*}1(0+1)^{*}1(0+1)^{*}$ で表せる。対応する右線形文法は 正規言語 の記事の例、有限オートマトンは 有限オートマトン の記事の例にある。
$0+1(0+1)^{*}$ は、先頭に不要な $0$ を付けない自然数の二進表現全体 $\{0\}\cup1\{0,1\}^{*}$ を表す。$(0+1)(0+1)^{*}$ は空でない文字列全体、$((0+1)(0+1))^{*}$ は偶数長の文字列全体、$(0+1)^{*}00$ は $00$ で終わる文字列全体を表す。
$(0+10)^{*}(1+\varepsilon)$ は、部分文字列 $11$ を含まない文字列全体を表す。実際、そのような文字列では各 $1$ の直後は $0$ であるか文字列の末尾であるから、文字列は $0$ と $10$ のブロックを並べたものの末尾に $1$ を付けるか付けないかの形に一意に分解できる。逆に、この形の文字列が $11$ を含まないことは明らかである。数え上げ関数は Fibonacci数になる（長さ $n$ の元の個数は $F_{n+2}$）。
$(0+1)^{*}\equiv(0^{*}1^{*})^{*}\equiv(0^{*}+1^{*})^{*}$ であり、$(01)^{*}0\equiv0(10)^{*}$、$(0+1)^{*}1\equiv(0^{*}1)^{+}$ である。最後の例では、$1$ で終わる文字列は最後の $1$ の手前で「$0$ の並びの後に $1$ が一つ」というブロックに一意に切り分けられる。二つの正規表現が同じ言語を表すかどうかは、対応する有限オートマトンを prop-regular-expression-to-automaton で作り、正規言語 の記事の決定問題の議論により判定できる。
$L=\{\,0^{n}1^{n}\mid n\in\mathbb{N}\,\}$ を表す正規表現は存在しない。実際、正規表現で表せる言語は prop-regular-expression-to-automaton により有限オートマトンで受理されるので正規言語であるが、$L$ は正規言語でない（正規言語 の記事の反例。反復補題による）。「$0^{*}1^{*}$ で表せる」と誤解しやすいが、この式は $0$ と $1$ の個数の一致を要求しない。すなわち $L$ は「$0^{*}1^{*}$ が表す言語の部分集合である」という性質は満たすが、「正規表現で表せる」という性質は満たさない。同様に、対応の取れた括弧列全体や回文全体も正規表現では表せず、これらは文脈自由文法で記述する（文脈自由言語）。
プログラミング言語やテキスト編集ソフトの「正規表現」は、本記事の正規表現に文字クラス（[0-9]）、回数指定（a{2,5}）、行頭・行末の指定などの略記を加えたもので、略記だけならば表せる言語の範囲は変わらない。しかし多くの実装は後方参照（((0+1)*)\1 のように「前に一致した部分と同じ文字列」を要求する機能）を持ち、この式は $\{\,ww\mid w\in\{0,1\}^{*}\,\}$ という正規でない言語を表すので、後方参照を含む式は本記事の意味での正規表現ではない。「実装の正規表現で書ける」ことは「正規言語である」ことを含意しない。
性質
代数法則
$\Sigma$ 上の任意の正規表現 $\alpha,\beta,\gamma$ について次が成り立つ。
- $(\alpha+\beta)+\gamma\equiv\alpha+(\beta+\gamma)$、$\alpha+\beta\equiv\beta+\alpha$、$\alpha+\emptyset\equiv\alpha$、$\alpha+\alpha\equiv\alpha$
- $(\alpha\beta)\gamma\equiv\alpha(\beta\gamma)$、$\varepsilon\alpha\equiv\alpha\varepsilon\equiv\alpha$、$\emptyset\alpha\equiv\alpha\emptyset\equiv\emptyset$
- $\alpha(\beta+\gamma)\equiv\alpha\beta+\alpha\gamma$、$(\alpha+\beta)\gamma\equiv\alpha\gamma+\beta\gamma$
- $(\alpha^{*})^{*}\equiv\alpha^{*}$、$\emptyset^{*}\equiv\varepsilon$、$\varepsilon^{*}\equiv\varepsilon$、$\alpha^{*}\equiv\varepsilon+\alpha\alpha^{*}$、$\alpha^{*}\equiv\varepsilon+\alpha^{*}\alpha$、$(\alpha+\beta)^{*}\equiv(\alpha^{*}\beta^{*})^{*}$
一方、$\alpha\beta\equiv\beta\alpha$ は一般には成り立たない。
$\equiv$ の定義により、各等式は対応する言語の等式に帰着する。(1) は和集合の結合律・交換律・$\emptyset$ が単位元であること・冪等性である。(2)、(3)、および (4) の $(\alpha^{*})^{*}\equiv\alpha^{*}$、$\alpha^{*}\equiv\varepsilon+\alpha\alpha^{*}$、$\alpha^{*}\equiv\varepsilon+\alpha^{*}\alpha$ は、形式言語 の記事の命題（言語の演算の基本法則）の (1)–(4) を $L(\alpha)$、$L(\beta)$、$L(\gamma)$ に適用したものである。$\emptyset^{*}=\{\varepsilon\}^{*}=\{\varepsilon\}$ は $L^{0}=\{\varepsilon\}$ と、$\emptyset^{n}=\emptyset$（$n\ge1$）、$\{\varepsilon\}^{n}=\{\varepsilon\}$ から従う。
$(\alpha+\beta)^{*}\equiv(\alpha^{*}\beta^{*})^{*}$：$A:=L(\alpha)$、$B:=L(\beta)$ とおく。$A\subset A^{*}B^{*}$（$a=a\varepsilon$）、$B\subset A^{*}B^{*}$ より $A\cup B\subset A^{*}B^{*}$ であり、Kleene 閉包は包含を保つ（$M\subset N$ なら $M^{n}\subset N^{n}$）ので $(A\cup B)^{*}\subset(A^{*}B^{*})^{*}$。逆に $A^{*}B^{*}\subset(A\cup B)^{*}(A\cup B)^{*}=(A\cup B)^{*}$ であるから、$(A^{*}B^{*})^{*}\subset((A\cup B)^{*})^{*}=(A\cup B)^{*}$ である（形式言語 の記事の命題 (3)）。
非可換性の例：$\Sigma=\{a,b\}$ で $L(ab)=\{ab\}\ne\{ba\}=L(ba)$ である。
これらの法則を用いると正規表現を書き換えて簡単にできるが、正規表現の等式の全体を有限個の等式公理だけから導くことはできず（Redko 1964。Sal66 の序論も参照）、$\alpha^{*}$ に関する推論規則（たとえば「$\alpha\equiv\beta\alpha+\gamma$ かつ $\varepsilon\notin L(\beta)$ ならば $\alpha\equiv\beta^{*}\gamma$」）を加えた公理系が知られている（HMU06 §3.4、Sal66）。
有限オートマトンとの往復
$\Sigma$ 上の任意の正規表現 $\alpha$ に対し、$L(\alpha)$ を受理する有限オートマトン（$\varepsilon$ 遷移を許す）$\mathcal{A}_\alpha$ が存在する。しかも $\mathcal{A}_\alpha$ は、受理状態がただ一つで初期状態と異なり、初期状態に入る遷移と受理状態から出る遷移を持たず、状態数が $\alpha$ の長さの $2$ 倍以下になるようにとれる。
$\alpha$ の構成に関する帰納法（構造的帰納法）で、主張の形の有限オートマトン（初期状態 $s$、唯一の受理状態 $f\ne s$、$s$ に入る遷移なし、$f$ から出る遷移なし。以下標準形という）を構成する。この構成は K. Thompson（Tho68）による。
基礎：$\emptyset$ には状態 $s,f$ と遷移なし（受理経路がなく $L=\emptyset$）。$\varepsilon$ には状態 $s,f$ と遷移 $s\xrightarrow{\varepsilon}f$（受理される文字列は $\varepsilon$ だけ）。$a\in\Sigma$ には状態 $s,f$ と遷移 $s\xrightarrow{a}f$（受理される文字列は $a$ だけ）。いずれも標準形である。
帰納：$\alpha,\beta$ に対して標準形の $\mathcal{A}_\alpha=(Q_\alpha,\Sigma,\Delta_\alpha,s_\alpha,\{f_\alpha\})$、$\mathcal{A}_\beta$ が得られているとし、状態の名前を付け替えて $Q_\alpha\cap Q_\beta=\emptyset$ とする。
- 連接 $(\alpha\beta)$：状態集合 $Q_\alpha\cup Q_\beta$、遷移 $\Delta_\alpha\cup\Delta_\beta\cup\{f_\alpha\xrightarrow{\varepsilon}s_\beta\}$、初期状態 $s_\alpha$、受理状態 $f_\beta$。$s_\alpha$ から $f_\beta$ への経路は、$f_\alpha$ から出る遷移が追加した $\varepsilon$ 遷移だけであり $s_\beta$ に入る遷移もそれだけなので、必ず「$s_\alpha$ から $f_\alpha$ への $\mathcal{A}_\alpha$ 内の経路、$\varepsilon$ 遷移、$s_\beta$ から $f_\beta$ への $\mathcal{A}_\beta$ 内の経路」の形をしており、ラベルは $uv$（$u\in L(\alpha)$、$v\in L(\beta)$）である。逆にそのような $u,v$ に対して経路が作れる。よって受理言語は $L(\alpha)L(\beta)$ で、標準形である。
- 和 $(\alpha+\beta)$：新しい状態 $s,f$ を加え、遷移 $\Delta_\alpha\cup\Delta_\beta\cup\{s\xrightarrow{\varepsilon}s_\alpha,\ s\xrightarrow{\varepsilon}s_\beta,\ f_\alpha\xrightarrow{\varepsilon}f,\ f_\beta\xrightarrow{\varepsilon}f\}$、初期状態 $s$、受理状態 $f$。$s$ からの経路は最初の $\varepsilon$ 遷移でどちらかの部品に入り、部品の間を移る遷移はないので、受理経路のラベルは $L(\alpha)\cup L(\beta)$ の元であり、逆も明らかである。標準形である。
- Kleene 閉包 $(\alpha)^{*}$：新しい状態 $s,f$ を加え、遷移 $\Delta_\alpha\cup\{s\xrightarrow{\varepsilon}s_\alpha,\ s\xrightarrow{\varepsilon}f,\ f_\alpha\xrightarrow{\varepsilon}f,\ f_\alpha\xrightarrow{\varepsilon}s_\alpha\}$、初期状態 $s$、受理状態 $f$。$s$ から $f$ への経路は、$s\xrightarrow{\varepsilon}f$ で直ちに終わるか（ラベル $\varepsilon$）、$s_\alpha$ に入って $f_\alpha$ に至り、$f_\alpha\xrightarrow{\varepsilon}s_\alpha$ で $0$ 回以上戻ってから $f_\alpha\xrightarrow{\varepsilon}f$ で終わる。$s_\alpha$ に入る遷移と $f_\alpha$ から出る遷移は追加したものだけなので、$s_\alpha$ から $f_\alpha$ への各区間は $\mathcal{A}_\alpha$ 内の経路であり、ラベルは $L(\alpha)$ の元である。よって受理言語は $L(\alpha)$ の元を $0$ 個以上並べた文字列全体 $L(\alpha)^{*}$ である。標準形である。
状態数について、基礎の $3$ 種は $2$ 状態、連接は状態を増やさず、和と Kleene 閉包は $2$ 状態増やすので、状態数は $\alpha$ に現れる記号（$\emptyset$、$\varepsilon$、$\Sigma$ の元、$+$、$*$）の個数の $2$ 倍以下である。
任意の有限オートマトン $\mathcal{A}$ に対し、$L(\mathcal{A})=L(\alpha)$ となる正規表現 $\alpha$ が存在する。
$\mathcal{A}=(Q,\Sigma,\Delta,q_0,F)$ とし、状態に番号を付けて $Q=\{q_1,\ldots,q_n\}$、$q_0=q_1$ とする（$\varepsilon$ 遷移があってもよい）。$0\le k\le n$ と $1\le i,j\le n$ に対し、$q_i$ から $q_j$ への経路であって、途中で通る状態（両端を除く）の番号がすべて $k$ 以下であるものを $k$-経路と呼び、$k$-経路のラベル全体を $R^{(k)}_{ij}\subset\Sigma^{*}$ とおく。$k$ に関する帰納法で、$R^{(k)}_{ij}$ を表す正規表現 $\rho^{(k)}_{ij}$ を構成する。
$k=0$：途中の状態を持たない経路は、長さ $0$ の経路（$i=j$ のときだけあり、ラベル $\varepsilon$）と $1$ 本の遷移 $(q_i,a,q_j)\in\Delta$（ラベル $a\in\Sigma\cup\{\varepsilon\}$）である。よって $\rho^{(0)}_{ij}$ を、$(q_i,a,q_j)\in\Delta$ となる $a$ すべての和（$\varepsilon$ 遷移は $\varepsilon$ として加える）とし、$i=j$ ならさらに $\varepsilon$ を加え、加えるものが一つもなければ $\emptyset$ とする。
$k\ge1$：$k$-経路は、$q_k$ を途中で通らない（このとき $(k-1)$-経路である）か、$q_k$ を途中で $1$ 回以上通る。後者の経路は、最初に $q_k$ に着くまでの区間、$q_k$ から $q_k$ へ戻る $0$ 個以上の区間、最後に $q_k$ を出てから $q_j$ に着くまでの区間に分けられ、各区間は途中で $q_k$ を通らないので $(k-1)$-経路である。逆に、これらの形の $(k-1)$-経路をつないだものは $k$-経路である。よって
$$R^{(k)}_{ij}=R^{(k-1)}_{ij}\cup R^{(k-1)}_{ik}\bigl(R^{(k-1)}_{kk}\bigr)^{*}R^{(k-1)}_{kj}$$
であり、$\rho^{(k)}_{ij}:=\rho^{(k-1)}_{ij}+\rho^{(k-1)}_{ik}\bigl(\rho^{(k-1)}_{kk}\bigr)^{*}\rho^{(k-1)}_{kj}$ が $R^{(k)}_{ij}$ を表す（$q_k$ から $q_k$ へ戻る各区間のラベルは互いに異なってよく、それを表すのが Kleene 閉包である）。
$n$-経路とは任意の経路であるから、$L(\mathcal{A})=\bigcup_{q_j\in F}R^{(n)}_{1j}$ であり、$\alpha:=\sum_{q_j\in F}\rho^{(n)}_{1j}$（$F=\emptyset$ なら $\alpha:=\emptyset$）が $L(\mathcal{A})$ を表す。
prf-regular-expression-from-automaton の手続きは Kleene（Kle56）の証明に基づくもので、$n^{3}$ 個の式を作るため手計算には向かない。実用上は、遷移のラベルに正規表現を許した一般化オートマトンを考え、初期状態でも受理状態でもない状態を一つずつ消去し、消去する状態 $q$ を経由する遷移 $p\xrightarrow{\rho_1}q$、$q\xrightarrow{\rho_2}q$、$q\xrightarrow{\rho_3}r$ を $p\xrightarrow{\rho_1\rho_2^{*}\rho_3}r$ にまとめる状態消去法がよく使われる（Sip12 Lemma 1.60、HMU06 §3.2.2）。数学的な内容は同じである。
$\Sigma$ 上の言語 $L$ について次は同値である。
- $L$ は正規言語である（右線形文法で生成される）。
- $L$ を表す正規表現が存在する。
- $L$ を受理する有限オートマトンが存在する。
- から (3) は prop-regular-expression-to-automaton、(3) から (2) は prop-regular-expression-from-automaton で示した。(1) と (3) の同値は 正規言語 の記事の命題（右線形文法と有限オートマトンの同値性）で証明する。正規表現の側から見ると、この定理は「正規言語のクラスは、有限言語を含み和・連接・Kleene 閉包で閉じた最小のクラスである」ことを意味する。したがって正規言語の閉包性（補集合・共通部分・鏡像など。正規言語 の記事の命題）は、正規表現の言語についての閉包性でもある。たとえば $L(\alpha)$ の補集合を表す正規表現はつねに存在するが、$\alpha$ から機械的に書き下す簡単な式はなく、有限オートマトンを経由して構成する。
補足
拡張された正規表現
正規表現に共通部分 $\alpha\cap\beta$ や補集合 $\lnot\alpha$ の記号を加えても、表せる言語のクラスは正規言語のままである（正規言語 の記事の閉包性）。一方、2 記号以上のアルファベット上で $\{\,ww\mid w\in\Sigma^{*}\,\}$ のような言語を表す拡張（後方参照）は正規言語の範囲を超える（rem-regular-expression-practical）。
歴史
正規表現は S. C. Kleene（Kle56）が神経回路網のモデルとしての有限オートマトンが受理する「事象」を記述するために導入し、有限オートマトンとの同値もそこで示された。文字列検索の道具としての実装は K. Thompson（Tho68）による。正規表現の等式の公理化は A. Salomaa（Sal66）による。標準的な教科書として HMU06 第 3 章、Sip12 §1.3、Igr11 第 3 章を挙げる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
