前回から、以下の本に沿って解説を書いている。
前回は、形式言語というものを扱った。
最小単位は記号で、その集合はアルファベット。
アルファベットに含まれる記号を並べたものを、そのアルファベット上の列。
そして、その列の集合が、形式言語ということだった。
今回ももちろんこのあたりの用語がガンガン出てくるので、不安な方は前回の記事と照らし合わせながら進めていこう。
前回の記事は以下だ。
さて、今回は正規表現を解説する。
正規表現は以前使い方を解説しているが、今回は形式言語に合わせた形で定義していく。
前回の最後に有限オートマトンもやると書いてしまったが、正規表現だけで長くなってしまったので、次回に回そう。
正規表現
前回、形式言語には制限を考えることが多いと書いた。
この正規表現は、この制限を表す方法の一つだ。
イメージとしては、この決まりにしたがって列を生成していく、という感じだろうか。
では、定義をしていこう。
\(\Sigma\)をアルファベットとし、\(\Sigma\)上の正規表現\(S\)と、その正規表現から生成される形式言語\(L(S)\)を以下のように定義する。
- \(\phi\)は正規表現であり、\(L(\phi) = \phi\)である。
- \(\varepsilon\)は正規表現であり、\(L(\varepsilon) = \{\varepsilon\}\)である。
- \(a \in \Sigma\)は正規表現であり、\(L(a) = \{a\}\)である。
- \(R_1, R_2\)を正規表現としたとき、以下3つを定義する。
- \((R_1 + R_2)\)は正規表現であり、\(L((R_1 + R_2)) = L(R_1) \cup L(R_2)\)である。
- \((R_1 \cdot R_2)\)は正規表現であり、\(L((R_1 \cdot R_2)) = L(R_1)L(R_2)\)である。
ただし、この\(\cdot\)は省略してもよい。 - \((R_1^*)\)は正規表現であり、\(L((R_1^*)) = L(R_1)^*\)である。
さて、これだけ見てもよく分からないと思うので、一つずつ見ていこう。
まず一つ目、\(\phi\)という記号は元々空集合を表していたが、正規表現にも使えると言っている。
その場合、その正規表現が表す形式言語も\(\phi\)である、ということだ。
二つ目、空列を表していた記号\(\varepsilon\)も正規表現として書くことができ、その場合には空列のみを持つ形式言語\(\{\varepsilon\}\)に対応する。
三つ目、ここからちょっと具体的な内容だ。
アルファベット\(\Sigma\)に含まれる記号\(a\)は正規表現で、そこから生成される言語はその記号を長さ1の列とみなしたもののみ含む。
ここまでの内容が基本的なものになり、四つ目に含まれる3条件で再帰的に正規表現を定義している。
では、その3条件を見ていこう。
まず条件4-1、二つの正規表現を加算記号\(+\)で挟み、その全体を小括弧で括ったものは正規表現だ。
そして、ここから生成される形式言語は、二つの正規表現で生成される形式言語両方の要素を持つものとなる。
例えば、\(a, b \in \Sigma\)に対して正規表現を\((a + b)\)と書いたとき、この形式言語は\(L(a) \cup L(b)\)となる。
条件3から、\(L(a) = \{a\}\)、\(L(b) = \{b\}\)と分かるので、\(L((a + b)) = \{a\} \cup \{b\} = \{a, b\}\)だ。
次に条件4-2、二つの正規表現を中点\(\cdot\)で挟む、あるいは連続して書き、それらを小括弧で括ったものは正規表現だ。
このとき、これで生成される形式言語は、それぞれで生成される形式言語の連接となる。
4-1の例と同じく、二つの記号\(a, b \in \Sigma\)で考えてみよう。
\((a \cdot b)\)、あるいは\((ab)\)と書いた場合、その形式言語は\(L(a)L(b)\)だ。
上にも書いたように、\(L(a) = \{a\}\)、\(L(b) = \{b\}\)となっている。
そして、復習で形式言語同士の連接を再掲しておこう。
$$L_1L_2 = \{l_1l_2 | l_1 \in L_1, l_2 \in L_2\}$$
これに従って考えてみると…
$$\begin{eqnarray}
L(ab) & = & L(a)L(b) \\
& = & \{l_1l_2 | l_1 \in \{a\}, l_2 \in \{b\}\} \\
& = & \{ab\}
\end{eqnarray}$$
となる、ということだ。
最後の条件4-3はスター演算だ。
正規表現に対してスター演算の記号を書き、それを括弧で囲めばそれも正規表現。
そして、それは言語に対するスター演算として定義されている。
今回は一つの正規表現なので、\(a \in \Sigma\)で見てみよう。
\((a^*)\)と書いたとき、\(L((a^*))\)を見てみると…
$$\begin{eqnarray}
L((a^*)) & = & L(a)^* \\
& = & L(a)^0 \cup L(a)^1 \cup L(a)^2 \cup … \\
& = & \{\varepsilon, a, aa, …\}
\end{eqnarray}$$
このように表現することができる。
ここまで、具体例として元となる正規表現を全て長さ1の列で見てきた。
しかし、実際にはこれが繰り返し適用されることにより正規表現となっている。
ということで、そのパターンの具体例を見てみよう。
例えば、アルファベットが\(\Sigma = \{0, 1\}\)のとき、正規表現を\(S = ((0 + (1 \cdot 1))^*)\)と書いたとする。
この正規表現\(S\)から生成される形式言語\(L(S)\)がどうなっているかを見ていく。
先に、これが本当に正規表現なのかから確認してみよう。
まず、この中に含まれる記号0, 1は条件3より正規表現だ。
次に、細かい単位から注目してみよう。
一つ目、\((1 \cdot 1)\)があり、1が正規表現なので条件4-2からここの部分は正規表現だ。
二つ目、\((0 +(1 \cdot 1))\)の部分も、加算記号の両側が正規表現なため、条件4-1からこれも正規表現。
三つ目、全体を見ると\(((0 + (1 \cdot 1))^*)\)で正規表現にアスタリスクがついて括弧で囲まれている、条件4-3から全体も正規表現と分かる。
では、これで生成される言語\(L(S)\)を見ていこう。
\(L((1 \cdot 1))\)について、これは連接なので\(L((1 \cdot 1)) = \{11\}\)だ。
\(L((0 +(1 \cdot 1)))\)、これは和集合となるので、\(L((0 +(1 \cdot 1))) = \{0, 11\}\)となる。
\(L(((0 + (1 \cdot 1))^*))\)はスター演算、つまり\(L(((0 + (1 \cdot 1))^*)) = \{0, 11\}^*\)。
これを具体的に書くと…
$$L(S) = \{\varepsilon, 0, 11, 011, 110, 00, …\}$$
こんな感じだ。
ちなみに、日本語で言うと、0,1の二つからなる列の集合で、条件として1は出現したら必ず偶数個連続する、という形式言語を想定したもの。
ちょっと長くなってしまったが、これが今回定義した正規表現だ。
優先順位と表記のルール
さて、上の例を見てもらえれば分かると思うが、括弧がやたら多い。
解説を書いている時も、対応が合っているか少し不安になってしまっていた。
そこで、条件4に含まれる三つの演算について、優先順位を決めて括弧を外せるようにしよう。
優先順位は高い順に\({}^*, \cdot, +\)とする。
また、これを無視してより高い優先順位にしたい際は、その範囲の括弧を残すこととしよう。
言い換えると、括弧についてはそこで一つの正規表現であることを強調していることとなる。
これを使うと、上の例である正規表現\(((0 + (1 \cdot 1))^*)\)は、\((0 + 11)^*\)となる。
なんとなく、見覚えのある形に近づいたと思う。
さて、もう3つほど表記を定義しよう。
まず、二つの正規表現に対する演算\(\cdot, +\)について、三つ以上並んでいた場合。
これらについては、結合律(前から演算するか、後ろから演算するかに依らず同じ結果になること)が成り立っているので、ここも括弧を省略していいとする。
例えば、\((1 \cdot 2) \cdot 3 = 1 \cdot 2 \cdot 3\)と書いていい、ということだ。
次に、スター演算\(R^*\)について。
これは意味を考えると、正規表現\(R\)が0回以上繰り返し出てくるという意味になるが、これを1回以上にしたい時がある。
そのとき、\(RR^*\)と書けば解決するのだが、これを\(R^+\)と書いていいこととしよう。
最後、同じ正規表現を指定回数書く場合。
例えば、ある正規表現\(R\)が5回出てくる場合、通常であれば\(RRRRR\)と書くのだが、これを\(R^5\)と表記できるようにしよう。
例題：郵便番号を表す正規表現
では、一つ例題を。
日本の郵便番号を表現する形式言語\(L(S)\)を、正規表現\(S\)を決定することによって求めてみる。
アルファベットは、0から9までの数字と、ハイフン。
そして、数字3桁、ハイフン、数字4桁と並んでいるもの全てを郵便番号とする。
実在するかどうかは考えなくていい、としておこう。
まず、各数字について、これは7か所いずれも0から9のどれかとなるので、そのうち1か所は…
$$0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9$$
と表せる。
ちょっと長いので、これを別の正規表現\(N\)と表すことにしよう。
次に、先頭からまずは数字3桁が並ぶので、\(N^3\)と書ける。
このとき、\(N\)単体で正規表現を構成しているので、代入する際は括弧が入ることに気を付けよう。
その後ろにハイフン、さらにその後ろに今度は数字が4桁来るので、最終的に…
$$N^3-N^4$$
で完成だ。
例題：加算のみ定義された数式を表す正規表現
もう一つ例題として、前回も考えた「足し算だけ定義されている数式」を表す形式言語を、今度は正規表現で作ってみる。
ただし、加算記号が正規表現側で特殊な意味を持つため、アルファベット内の加算記号はダブルクォーテーションで囲むこととしよう。
さて、まずはこの数式の構造を見るのだが、前回見たように先頭から1桁以上の数字、加算記号、1桁以上の数字、…と並んでいることが分かる。
また、加算記号、数字はセットで0回以上繰り返されるというのも前回見た通りだ。
ということで、まずは1桁以上の数字を表す正規表現を作っていこう。
とはいえ、上の郵便番号の例を見てもらえればすぐに分かると思う。
同じように、数字一桁を表す正規表現を\(N\)とすると、1桁以上の数字は\(N^+\)だ。
今回は0個はNGなので、アスタリスクではなくプラスであることに注意。
次に、これまた前回同様に、加算記号、数字の1組分を表す正規表現を作る。
これは単に繋げるだけなので、\(“+”N^+\)でOKだ。
最後、今度はこれが数字の後ろに0回以上繰り返されるので…
$$N^+(“+”N^+)^*$$
これで完成となる。
おわりに
今回は、形式言語に合わせた形で正規表現を解説した。
色々書いてきたが、正規表現は形式言語を生成するためのルール、というイメージを忘れないようにしよう。
次回は、今回解説できなかった有限オートマトンを解説していく。
…中身を先に見たのだが、これまた長くなりそうなので、複数に分割することとなるだろう。
多分あまり見たことがないものが続々と出てくると思うので、慎重に進めていこう。
2020/11/28追記
次回の内容を更新した。
最初、全てを1記事にしようとしていたのだが、やはり長くなりすぎたので分割して投稿することにした。
…時間が数日もかかったのはそれが原因だ。
まずは有限オートマトンとは何かを解説した。
中で紹介している状態遷移図を書けばかなり分かりやすくなるので、是非手を動かしてもらいたい。
コメント