正規表現

正規表現は、語の集合を表すことのできる文字列です。正規表現は、有限オートマトンを簡単に表す方法と考えることもできます。

正規表現とは

算術では、· や + のような記号を使って、例えば (2 + 3) · 4 のような式をつくります。この式を計算すると、数が得られます。正規表現は、文字といくつかの特別な記号を並べたもの（例えば a(x ∪ y)）で、これを評価すると（形式）言語が得られます。式 (2 + 3) · 4 の結果は20という数で、正規表現 a(x ∪ y) の結果は2つの語「ax」「ay」からなる集合です。

前の正規表現 a(x ∪ y) は、どのように評価すればよいでしょうか。実は、それぞれの文字は、その文字だけを要素とする集合（要素が1つの集合）の略記で、省略されたかけ算は語の連接を表します。この正規表現を省略せずに書くと、次のようになります。

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

これを次のように評価します。和集合 {x} ∪ {y} から言語 {x,y} ができます。言語 {a} と {x,y} を連接すると、言語 {ax, ay} が得られます。

正規表現はプログラミングでとてもよく使われ、ほとんどのプログラミング言語に何らかの形で実装されています。例えば、利用者が入力したテキストが一定の条件を満たすか（有効なメールアドレスか、正しい日付かなど）を確かめたり、テキストを置換したり（例えば、テキスト中のURLをすべてクリックできるリンクに置きかえるなど）するのに使われます。

実際の正規表現の実装は、たいていここで説明する正規表現よりも強力で、構文も少し異なるうえ、何よりずっと複雑です。

正規表現の定義

正規表現は、あるアルファベット Σ 上で定義します。次のものを正規表現といいます。

1. a（ただし a ∈ Σ）。つまり、アルファベットの文字1つだけでも正規表現です。
2. ϵ：空語です。プログラミングでは空文字列といい、引用符を2つ並べただけの 「」 とも書きます。
3. ∅：正規表現は空の言語も表せなければならないので、空の言語も正規表現です。
4. (R₁ ∪ R₂)（ただし R₁, R₂ は正規表現）。
5. (R₁ ∘ R₂)（ただし R₁, R₂ は正規表現）。
6. (R^∗)（ただし R は正規表現）。

4番の記号 ∪ の代わりに、縦棒の記号 | を使うこともできます。記号 ∘ の代わりには、何も書かなくてかまいません。かけ算の記号の点 · をふつう書かないのと同じように、連接の記号 ∘ もふつうは書きません。そのため、正規表現 a ∘ (b ∪ c) と a(b|c) は同じものです。

それぞれの演算子は何を表すでしょうか。

• ∪ または | は言語の和集合を表します。
• ∘ は言語の連接を表します。
• ^∗ は言語のクリーネ閉包を表します。

例：

• a は、単純な言語 {a} を表します。
• a|b は、2つの語からなる言語 {a, b} を表します。
• a ∘ b は、言語 {ab} を表します。
• a(b|c)d は、言語 {abd, acd} を表します。
• a(b^∗) は、文字「a」で始まり、そのあとに文字「b」が任意の個数続くすべての語の言語を表します。
• (ab)^∗ は、すべての語 {ϵ, ab, abab, ababab, …} からなる言語を表します。
• 0^∗10^∗ は、0と1からなる語のうち、1をただ1つ含むすべての語の言語を表します。（この式は (0^∗)1(0^∗) と書くほうが正確ですが、括弧がなくても読みやすいときは省略できます。）
• Σ^∗1Σ^∗ は、1を少なくとも1つ含むすべての語の言語を表します。
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ は、すべての自然数（を表す語）の言語を表します。

これから、正規表現と有限オートマトンが等価であることを示していきます。評価すると言語 R になるどの正規表現についても、ある有限オートマトン A が存在して L(A) = R が成り立ちます。その逆も成り立ちます。

参考文献

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools