突然だが、プログラムを作りたくなった。
やりたいことは、文字列として入力された数式をプログラムで解釈し、計算すること。
ただやるだけであれば、BNFを作ってそれをプログラムに落とし込めばいい。
そこで、BNFをもう一度しっかり勉強しようとしたら、今度は文脈自由文法という言葉が出てきた。
このあたりからちょっと頭が混乱してきたので、一から勉強し直そうと思う。
本シリーズは、その勉強結果をまとめたものである。
段ボールから参考書を引っ張り出してきたので、それに沿って進めていこう。
参考書は以下だ。
今回は、導入ということで形式言語を解説する。
これは一般的に言う言語とは異なるので、そこに注意しながら読み進めてもらいたい。
2020/12/14追記
本シリーズでは、集合や論理の知識を前提としている。
そのあたりが不安な方は、別で解説を書いたので、そちらを参照頂きたい。
言語とは
さて、なぜ数式の解釈なのに言語なんだ、と思うだろう。
やりたいこととしては、数式の構造を定式化し、プログラムを組む際の参考にしたい。
冒頭にちらっと名前を出したBNFは、この構造を定式化したものを表記する方法の一つだ。
そのために、これから考える言語というものを使う、ということになる。
上にも書いたが、ここでの言語は、一般的な日本語や英語といった言語に限らない。
ここから、日本語や英語といった普段我々が使う言語のことを自然言語、これから説明する言語を形式言語と呼ぶことにする。
では、形式言語を小さい順に説明しよう。
記号・アルファベット
形式言語を構成する最小単位の文字を記号と呼び、この記号を集めたもの…つまり、記号の有限集合をアルファベットと呼ぶ。
当然、通常の意味でのアルファベットも含められるし、数字だったり記号なんかも含めることができる。
このアルファベットを表す際には、記号\(\Sigma\)(読み：シグマ)がよく使われる。
列
この\(\Sigma\)上の列とは、これに含まれる記号を1列に並べたものを言う。
例えば、\(\Sigma = \{0, 1\}\)なら、0と1で構成された文字列…例えば10101などが列となる。
呼び方なのだが、列以外にも、記号列や文章という名前もある。
ここから、基本的には列と呼ぶことにしよう。
形式言語
そして、形式言語とは、この\(\Sigma\)上の列の集合のことだ。
…とはいえ、ここまでの書き方ではさっぱり分からないと思う。
そこで、具体的に数式を題材にして形式言語を説明してみる。
まず、0から9の数字と四則演算の記号、そして括弧などが記号だ。
これをまとめた集合\(\Sigma\)がアルファベットとなる。
具体的に書くと、以下のようなイメージだ。
$$\Sigma = \{0, 1, 2, 3, 4, 5, 6 ,7 ,8 ,9, +, -, *, /, (, )\}$$
そして、この組み合わせが列となる。
例えば、1+2は列だし、15-3(2 + 3)*2も列だ。
なお、今回は累乗や階乗を定義していないので、2^3や5!などは列にはならない。
そして、こういった列全てを集めた集合が、形式言語となる。
…のだが、今説明した範囲では、記号の組み合わせ方について何の制約もつけていない。
つまり、+や、++-+2*/4-+1**2みたいなものも含まれてしまっている。
そうではなく、通常は何らかの性質を持った列の集合を考えることが多い。
その場合の書き方もあるのだが、後で説明する(一般的な意味での)記号があった方が具体例を理解しやすいので後に回そう。
ということで、細かい用語を色々と説明していく。
列の長さ
ある列に含まれる記号の数をその列の長さと呼び、列を\(x\)としたときに、\(|x|\)でその列の長さを表す。
例えば、\(\Sigma = \{0, 1\}\)上の列\(x = 110001\)について、\(|x| = 6\)だ。
特別な列として、長さ0の列がある。
これは空列と呼び、通常\(\varepsilon\)(読み：イプシロン)で表される。
また、負の長さの列は考えない。
列の逆
ある列\(x\)について、それに含まれる記号を逆順に並べたものを、列\(x\)の逆と呼び、\(x^R\)で表す。
例えば、\(x = 11100\)について、\(x^R = 00111\)だ。
言葉ではカンタンに分かると思うが、数式で扱うにはこの定義方法はあまり良くない。
後半で厳密に定義してあるので、よかったらそちらも参考にしてほしい。
なお、今後記号\(a \in \Sigma\)に対する逆\(a^R\)を考えることがある。
このときは、この記号\(a\)を長さ1の列と見なすことで問題なく議論を進められる。
一応使う際には補足を入れようとは思うが、覚えておいて欲しい。
列の連接
二つの列\(x\)と\(y\)を並べたものを連接と呼び、単に繋げて\(xy\)と書く。
ただし、この連接という演算を強調して\(x \cdot y\)と表記することもある。
例えば、\(\Sigma = \{0, 1\}\)上の列\(x = 110\)、\(y = 010\)の連接\(xy\)は\(110010\)となる。
今、二つの列の連接しか解説していないが、三つ以上も当然書ける。
そのとき、どの二つから連接させても問題ない。
例えば、\(xyz\)という連接を考えるとき、先に\(xy\)で連接させ、その後ろに\(z\)を連接させたものと、\(yz\)を先に連接させておいて、その前から\(x\)を連接させたものは等しいということ。
数式で書くなら以下のような感じ。
$$xyz = (xy)z = x(yz)$$
これは結合律と呼ばれる性質だ。
そして、空列\(\varepsilon\)については、任意の列\(x\)について\(x \varepsilon = \varepsilon x = x\)を満たす。
0文字を足すということは、結局何もしないのと同じだ。
なお、ある列\(x\)を複数連接させたものについて、その連接させた列\(x\)の個数\(n\)を使って\(x^n\)と書く。
通常の計算と同じように、\(xx = x^2\)となるイメージだ。
\(x = 10\)のときは、\(x^2 = 1010\)となる。
ちなみに、逆と同じく記号との連接も考えることができる。
このとき、記号は長さ1の列として見てみよう。
部分列
ある列\(x\)の一部分を、\(x\)の部分列という。
例えば、110010に対して、100は部分列だ。
厳密に書くと、ある列\(w\)が\(xyz\)と表せるとき、列\(y\)を\(w\)の部分列という、となる。
このとき、どの文字も空列\(\varepsilon\)であってもいい。
上の110010に対する100では、\(x = 1\)、\(y = 100\)、\(z = 10\)となっている。
形式言語の性質
さて、形式言語の性質の表記方法を説明しよう。
形式言語も集合なので、集合の定義方法に則って書いていく。
$$\{性質 | 性質の条件\}$$
こんな書き方だ。
例として、記号\(\Sigma = \{0, 1\}\)上の列において、まず0がある回数出現し、その後同じ数の1が出現するという形式言語を考える。
これを表現すると、以下のように書くことができる。
$$\{0^n1^n | n \geq 0, n \in \mathbb{Z}\}$$
まず、縦棒の右側から、\(n\)は0以上の整数だ。
そして左側を見ると、記号0が\(n\)回、次に記号1が\(n\)回出てくるという表記になっている。
連接で補足したように、記号は長さ1の列であると見なせるので、この書き方で問題ない。
このとき、実際には具体的な\(n\)の値によってできた列全てがこの集合に含まれることになる。
例えば…
$$\varepsilon, 01, 0011, 000111, …$$
といった列が具体的に含まれることになる。
\(\Sigma\)上の特殊な形式言語
さて、この制限をつけなかった場合でも、立派な形式言語となりうる。
この場合、形式言語はそのアルファベット\(\Sigma\)で構成される任意の文字列、ということになる。
これを表す場合、\(\Sigma^*\)と表記する。
これには、0個の記号からなる列…つまり空列\(\varepsilon\)も含まれることに注意しよう。
逆に、全ての列を含まないとする形式言語も考えることができる。
このとき、通常の集合と同じく、空集合を表す\(\phi\)(読み：ファイ)を使う。
一つ注意点として、空列のみを持つ形式言語\(\{\varepsilon\}\)は、\(\phi\)とは異なる。
混同しやすいので気を付けよう。
形式言語同士の連接
ここまで、一つの形式言語にのみ注目してきた。
ここから、複数の形式言語に対する考え方を見ていこう。
二つの列に対して連接を考えたように、二つの形式言語に対する連接も考えることができる。
\(L_1, L_2\)をそれぞれ形式言語とし、この二つの連接を\(L_1L_2\)、もしくは\(L_1 \cdot L_2\)と表記して、以下のように定義する。
$$L_1L_2 = \{l_1l_2 | l_1 \in L_1 , l_2 \in L_2\}$$
要するに、\(L_1\)に含まれる任意の列と\(L_2\)に含まれる任意の列を連接させたもの全部の集合を、二つの形式言語の連接と定義する。
例えば、\(L_1 = \{00, 01\}, L_2 = \{10, 11\}\)としたとき…
$$L_1L_2 = \{0010, 0011, 0110, 0111\}$$
となる。
なお、ここでも一つ注意があり、空集合\(\phi\)で表される形式言語について、任意の形式言語\(L\)と連接させると、その形式言語も空集合となる。
$$L\phi = \phi L = \phi$$
この理由は単純で、形式言語の連接の定義を見ると、二つの形式言語に含まれる列を連接させたものの集合となっている。
そして、\(\phi\)は要素を持たない。
よって、\(x \in \phi\)となる\(x\)が存在しないので、結局連接させようがない、つまり空集合となるのだ。
普通の感覚では\(L\)となりそうだが、\(L\)になるのは空列のみを持つ形式言語\(\{\varepsilon\}\)との連接だ。
$$L \{\varepsilon\} = \{\varepsilon\} L = L$$
ここで、同じ形式言語の連接も見てみよう。
列のときと同じように、ある形式言語\(L\)を連接させたものについて、その連接させる個数\(n\)を使って\(L^n\)と書く。
このとき、\(L^1 = L\)、\(L^0 = \{\varepsilon\}\)と決められている。
また、以下の式で\(L^*\)を定義する。
$$L^* = L^0 \cup L^1 \cup L^2 \cup …$$
要するに、形式言語\(L\)を任意回連接させたもの全ての和集合だ。
この*をスター演算と呼ぶことがある。
足し算のみを含む数式の形式言語
では、ここまでの内容を使って、「足し算だけ定義されている数式」を表す形式言語を作ってみよう。
まず、使用する記号は0から9までの数字と加算記号+なので、アルファベットは以下のようになる。
$$\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +\}$$
これでもいいのだが、後の都合上、二つに分けよう。
まず、数字のみを含むアルファベットを\(\Sigma_1\)とする。
$$\Sigma_1 = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$
そして、加算記号は別のアルファベット\(\Sigma_2\)にしよう。
$$\Sigma_2 = \{+\}$$
次に、足し算を分解して先頭から見てみる。
先頭には数字が来て、二桁以上も考えると数字が任意回繰り返されることになるので、\(\Sigma_1^*\)で表せる。
…としたいのだが、これには空列\(\varepsilon\)も含むので、これを取り除いて\(\Sigma_1^* \setminus \{\varepsilon\}\)としよう。
この記号\(\setminus\)は差集合といって、左の集合から右の集合に含まれる要素を取り除いたものと定義されている。
二つの集合\(A, B\)について、\(A \setminus B\)を数式で表せば以下の通りだ。
$$A \setminus B = \{x | x \in A, x \not in B\}$$
なお、今回は関係ないが、\(B\)が\(A\)の部分集合になってなくてもよい。
本題に戻って…\(\Sigma_1^*\)から空列\(\varepsilon\)を取り除いた列の集合に\(N\)という名前をつけておく。
$$N = \Sigma_1^* \setminus \{\varepsilon\}$$
…実は、これだと0003みたいに先頭から0が連続するようなものも表せてしまうのだが、それを弾こうとすると長くなってしまうので今回は許容する。
これで、数字を\(N\)という形式言語で表せるようになった。
次に、この後ろには加算記号、数字の組が任意回現れる。
具体的に見ると、1 + 2 + 3の場合には、1、+ 2、+ 3といった感じで分けることができる。
もちろん、一つの数字だけでも式としていいので、0回以上だ。
これを表すために、先に加算記号、数字の組で構成される形式言語を作ってしまおう。
あとは、それに対してスター演算をしてあげれば任意回を表現できる。
この加減記号、数字の組を1組分表す形式言語を\(L\)とし、以下で定義する。
$$L = \{xy | x \in \Sigma_2, y \in N\}$$
あとは、これが数字の後ろで任意回繰り返されるので、上記の通りスター演算を使って…
$$NL^*$$
で完成だ。
なお、\(\Sigma_2\)に減算記号-を入れれば加減算になるし、形だけ見れば乗算*、除算/を入れることで加減乗除の式にすることもできる。
…のだが、乗除に関しては計算順序が異なるので、それも表現したい場合はちょっと細工が必要になる。
単に数式かどうかだけ判定したい場合にはそこまでは不要だが、今後解釈して計算するとなると、そこまで考えたい。
今その計算順序まで考えてしまうと色々複雑になってしまうので、今回はやめておこう。
本の例題を見てみる
最後に、ここまでの内容で本に紹介されている例題を見ていこう。
列の逆をより厳密に定義
上で、ある列\(x\)を逆順にしたものを逆と呼び、\(x^R\)で表すと書いた。
これを、より厳密に定義しよう。
あるアルファベット\(\Sigma\)上の列\(x\)について、記号\(a \in \Sigma\)を使って\(x = ay\)と表せるとしよう。
\(x\)の先頭一文字を取って、それを\(a\)としたイメージだ。
この\(a\)は本来記号だが、上の紹介で書いた通り長さ1の列とみなして以降議論を進める。
このとき、列\(x\)の逆は、以下二つの式で再帰的に定義できる。
- \(\varepsilon^R = \varepsilon\)
- \((ay)^R = y^Ra\)
これが何を言っているか、長さ3程度の列で具体的に計算してみよう。
今回考える列を\(abc\)とする。
念のため、この\(a, b, c\)は、変数ではなく具体的な記号(長さ1の列)だ。
この逆を見ていくと…
$$\begin{eqnarray}
(abc)^R & = & (a(bc))^R\\
& = & (bc)^R \cdot a \\
& = & c^R \cdot b \cdot a \\
& = & (c \varepsilon)^R \cdot b \cdot a \\
& = & \varepsilon^R \cdot c \cdot b \cdot a \\
& = & \varepsilon \cdot c \cdot b \cdot a \\
& = & c \cdot b \cdot a \\
& = & cba
\end{eqnarray}$$
という感じで、逆が導き出せる。
連接された列の逆
これは定理だ。
二つの列\(x, y\)の連接の逆\((xy)^R\)は、以下の式で表される。
$$(xy)^R = y^Rx^R$$
上で説明した逆の定義とは違い、今回はそれぞれ列\(x, y\)の長さを指定していないことに気を付けよう。
これは定理なので、証明が必要だ。
\(xy\)の長さに関する数学的帰納法で証明していこう。
まず、長さが0のとき。
このときは、\(x = y = \varepsilon\)しかあり得ない。
これを使って具体的に計算すると、まず左辺について…
$$(xy)^R = (\varepsilon \varepsilon)^R = \varepsilon ^R = \varepsilon$$
次に、右辺について…
$$y^Rx^R = \varepsilon ^R \varepsilon ^R = \varepsilon \varepsilon = \varepsilon$$
より、成立だ。
次に、\(|xy| = n\)の時に命題が成立していると仮定する。
このとき、先頭に一文字の列\(a\)を足して、\((axy)^R\)を見ていこう。
\(ax = x’\)として、\((x’y)^R = y^Rx’^R\)を示せばいい。
ここで場合分けをする。
まず、\(x = \varepsilon\)のとき、\((ay)^R = y^Ra^R\)となるか見ていく。
左辺について、\(a\)は長さ1の列なので、逆の定義から\((ay)^R =y^Ra\)と表せる。
右辺について、\(a\)は長さ1の列なので、明らかに\(a^R = a\)だ。
よって、\(y^Ra^R = y^Ra\)なので、両辺等しい。
最後に、\(x \not = \varepsilon\)の場合について見ていこう。
まず、左辺。
$$\begin{eqnarray}
(x’y)^R & = & (axy)^R \\
& = & (a(xy))^R \\
& = & (xy)^Ra \\
& = & y^Rx^Ra
\end{eqnarray}$$
2行目→3行目の変換は\(|a| = 1\)より逆の定義を、3行目→4行目の変換は\(|xy| = n\)より帰納法の仮定を使った。
そして、右辺。
$$\begin{eqnarray}
y^Rx’^R & = & y^R(ax)^R \\
& = & y^Rx^Ra
\end{eqnarray}$$
これも両方等しくなった。
以上から、命題は正しいと証明できた。
鳩ノ巣原理
本に紹介が載っているので、ここでも触れておこう。
鳩ノ巣原理とは、鳩が\(n + 1\)羽以上いて、その鳩たちを\(n\)個の巣箱に入れていく場合に、必ずいずれかの巣箱には鳩が2匹以上いる(全ての鳩を1羽ずつ箱に入れるのは不可能)という定理だ。
これを応用した例題が紹介されている…のだが、ちょっと別の例題を紹介しよう。
東京都には、この記事を書いている時点で約927万人が住んでいる。
このとき、ある瞬間において、髪の毛の本数が全く同じ人の組が東京都内に必ず存在することを示せ、というもの。
前提として、髪の毛は一人あたり最大でも15万本としてよい。
このとき、927万人を番号付きの部屋に分けるところを想像してみよう。
ある瞬間なので、それぞれの人の髪の毛の本数は決まっている。
そのときの髪の毛の本数を番号とする部屋に入ってもらおう。
髪の毛の本数は最大でも15万本なので、部屋は0番から15万番まで用意すればいい。
このとき、鳩ノ巣原理が使える。
人を鳩、部屋を巣箱に置き換えると、927万羽の鳩に対し、15万1個の巣箱となる。
明らかに、一羽ずつでは入りきらないだろう。
よって、ある瞬間においてまったく同じ本数の髪の毛の人は存在する、と言えるのだ。
おわりに
今回は、形式言語というものを解説してきた。
これが出発点となり、他に色々なものを定義していくことになる。
まだイメージが湧きづらいと思うが、具体例などを作りながら理解を深めていこう。
次回は、正規表現と有限オートマトンというものを解説する。
正規表現は以前講座で解説しているが、そのときのような具体的な書き方ではなく、今回の形式言語の形で定義していく。
有限オートマトンについては初めての内容になる。
今回の形式言語ももちろん出てくるので、不安なら今回の記事と併せて読み進めていこう。
2020/11/24追記
次回にあたる正規表現編を公開した。
…長くなってしまったので、有限オートマトンは次々回以降に回した。
ちょっと複雑になってきたので、落ち着いて一個一個理解していこう。
コメント