タイトルに「正規表現とオートマトン：」が付いた記事は、いちおう続きものになる予定です。「この機会にマスターしようぜ、正規表現、構文図、オートマトン」から始まる形式言語理論入門シリーズだともいえますが、これから扱う話題はあまり一般的じゃありません。特論ですな。「Catyの正規表現型：なぜ明瞭正規表現なのか」で触れた明瞭正規表現についてハッキリと述べることが目的です。この目的に必要な概念や手法を順に説明していきます。
今日はイプシロン指標の話です。「イプシロン指標」は僕の造語です。とても重要な概念の割には名前がないので命名しました。でも、ある種の対象物／概念にε（イプシロン）という記号を使うことは伝統的なのです。
内容：
言語、オーマトン、正規表現
アルファベット、つまり基本記号の集合をAとしましょう。例えば、A = {a, b, c}。アルファベットAに属する記号から構成される列を、エンドマーカー記号で終わるリスト、例えば [a, b, a, c, $] で表します。でも、この記法で書くのは面倒なので "abac" という文字列形式も使います。
アルファベットAから構成できるすべての記号列の集合は A* と書きます。形式言語理論で「アルファベットA上の言語」といったら、それは単にA*の部分集合のことです。
- LはアルファベットA上の言語 ⇔ L⊆A*
Mはオートマトンとしましょう。「この機会にマスターしようぜ、正規表現、構文図、オートマトン」で述べたような方法でMが受理する記号列の全体を Lang(M) と書くことにします。
- x∈Lang(M) ⇔ xはオートマトンMにより受理される
正規表現からオートマトンを作る方法はいろいろあるので、オートマトンを作るアルゴリズムを1つ決めて、それによって正規表現Eから構成されるオートマトンを Autom(E) と書くことにします。Lang(E) を Lang(Autom(E)) として定義します。M = Autom(E), L = Lang(E) = Lang(M) とすると：
正規表現に対するLang(E)は、オートマトンを経由せずに直接定義することもできます（後述）。
イプシロンの話
記号を1個も含まない空な列をεで表します。つまり、ε = [$] = "" です。空列εだけからなる集合もεと書く習慣があります。これはトンデモナイ話で、ε = {ε} というワケわからん等式が成立します。それだけでなく、「何もない」という目印にεを使ったりもします。
混乱しそうなので、{ε}は1（太字のイチ）で示します。0は空集合です。「空列だけからなる集合」と「空集合」は全然別物ですから気を付けてください。1 = {ε} も 0 = {} も A* の部分集合なので言語です。Aが何であっても、1⊆A*、0⊆A* は保証されます。
ε = {ε} は使いませんが、ここでは、文字「ε」を別な意味でオーバーロードします。Lが言語、つまり記号列の集合のとき、ε(L) を次のように定義します。
- ε∈L のとき、ε(L) = 1
- ε∈L でないとき、ε(L) = 0
つまり、ε(L)は、「Lに空列εが含まれるか？」に対して 1（true）または 0（false）で答えた値です。この ε(L) を、Lのε指標（イプシロン指標）と呼ぶことにします。Lにε(L)を対応させる関数εもイプシロン指標といいましょう。
言語演算とε指標
x, yが記号列だとして、xとyの連接を x・y、または単に xy で示します。例えば、"Hello"・"World" = "HelloWorld"。明らかに次が成立します。
- x ≠ ε または y ≠ ε ならば、xy ≠ ε
待遇をとれば*1：
- xy = ε ならば、x = ε かつ y = ε
この事実から、ε(K・L) = ε(K)ε(L) が成立します；って、ちょっと唐突か？ 以下に説明します。
KとLがA上の言語のとき、x∈K と y∈L から作った x・y を全部寄せ集めた集合が K・L です。
- K・L = {x・y | x∈K, y∈L}
あるいは：
- K・L = {z | z = x・y となる x∈K, y∈L が存在する }
例えば、K = {"a", "ab", "bab"}、 L = {"cc", ""} ならば、
- K・L = {"a"・"cc", "ab"・"cc", "bab"・"cc", "a"・"", "ab"・"", "bab"・""} = {"acc", "abcc", "babcc", "a", "ab", "bab"}
この状況で、ε∈K・L ということは、ε = x・y となる x∈K と y∈L が存在することですが、それは x = ε、y = ε に限られます。つまり：
- ε∈K・L ⇔ ε∈K かつ ε∈L
ε指標を使うと：
- ε(K・L) = 1 ⇔ ε(K) = 1 かつ ε(L) = 1
- ε(K・L) = 0 ⇔ ε(K) = 0 または ε(L) = 0
これは ε(K・L) = ε(K)ε(L) であることを意味します。右辺の ε(K)ε(L) は数の掛け算ですが、1をtrue、0をfalseとみなしての論理ANDでもあるので、次のようにも書けます。
- ε(K・L) = ε(K)∧ε(L)
ε指標の計算
ε指標に関して次の計算法則が成立します、∨は論理ORです*2。
- ε(0) = 0
- ε(1) = 1
- ε(K・L) = ε(K)∧ε(L)
- ε(K∪L) = ε(K)∨ε(L)
ε(K・L) = ε(K)∧ε(L) 以外の等式もすぐに確認できるでしょう。
正規表現Eに対して、ε(E) = ε(Lang(E)) とすれば、正規表現のε指標を定義できます。このとき、オートマトンを経由しないで、Lang(E) を定義しておくと便利です。
- aが基本記号のとき、Lang(a) = {"a"}
- Lang(E, F) = Lang(E)・Lang(F)
- Lang(E | F) = Lang(E)∪Lang(F)
- Lang(E?) = Lang(E)∪1
- Lang(E*) = Lang(E)*
一番最後の Lang(E)* は、L = Lang(E)* として、1 ∪ L ∪ L・L ∪ L・L・L ∪ ... のことです。
以上の公式を組み合わせれば、正規表現に対するε指標の計算法則が得られます。
- aが基本記号のとき、ε(a) = 0
- ε(E, F) = ε(E)∧ε(F)
- ε(E | F) = ε(E)∨ε(F)
- ε(E?) = 1
- ε(E*) = 1
((a | b)*, c) という正規表現のε指標を計算してみましょう。
ε((a | b)*, c)
= ε((a | b)*)∧ε(c)
= ε((a | b)*)∧0
= 1∧0
= 0
ε指標の使いどころ
明瞭正規表現を定義したり判定したりするには、与えられた正規表現Eに対して First(E), FollowLast(E) などの値（値とはいえ集合です）を計算しなくてはならないのですが、このとき ε(E) がやたらに登場します。
