7.2 括弧からなるバランスの取れた文字列
\(\left\{ {\color{blue} \,\textbf{\textsf{]}}\,}, {\color{red} \,\textbf{\textsf{[}}\,} \right\}^{\ast}\) を角括弧だけからなる文字列全体の集合とする。例えば、次の二つの文字列は \(\left\{ {\color{blue} \,\textbf{\textsf{]}}\,}, {\color{red} \,\textbf{\textsf{[}}\,} \right\}^{\ast}\) に属する:
\[ {\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}, \qquad {\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,} \tag{7.1}\]
文字列 \(s \in \left\{ {\color{blue} \,\textbf{\textsf{]}}\,}, {\color{red} \,\textbf{\textsf{[}}\,} \right\}^{\ast}\) のバランスが取れている (matched) とは、括弧が通常の意味で「マッチする (対応が取れている)」ことを言う。例えば、上記の例で左側にある文字列を考えると、三文字目の右角括弧に対応する左角括弧が存在しないので、この文字列はバランスが取れていない。これに対して右側にある文字列はバランスが取れている。
本節では、再帰的に定義された集合と関数を利用してバランスが取れた文字列に関する性質を定義・証明する方法をいくつか示す。定義・証明される性質は当たり前に思えるものばかりなので、本当に情報科学における重要性があるのかと疑問に思うかもしれない。この疑問に対する正直な答えは「現在ではあまり重要でなくなった」である。次の文章で説明されるように、こう言える理由には情報科学における偉大な成功が関係している:
情報科学が誕生して成長しつつあった 1950 年代から 1960 年代にかけて、この分野で中心的な問題は実用可能なプログラミング言語の作成だった。そしてプログラムをコンパイルする上で鍵となっていたのが算術式のパースである。重要な問題の一つが、次に示すような式を受け取って評価順序を表す括弧を正しく付ける問題だった:
\[ x + y \ast z^{2} \div y + 7 \]
括弧を付ける方法はいくつも考えられる:
\[ [[x + y] \ast z^{2} \div y] + 7 \]
\[ x + [y \ast z^{2} \div [y + 7]] \]
\[ [x + [y \ast z^{2}]] \div [y + 7] \]
\[ \vdots \]
Robert W. Floyd が Turing 賞 (情報科学におけるノーベル賞) を受賞したとき、受賞理由の一つは算術式に対して括弧を正しい位置に付ける単純な手続きの発見だった。
1970 年代から 1980 年代にかけて、こういったパース技法は式の文法からパーサーを自動的に生成する高レベルなコンパイラコンパイラにパッケージ化された。このパースの自動化があまりにも有用だったので、この分野は次第に注目されなくなっていった。1990 年代には、パース技法は多く情報科学のカリキュラムから姿を消した。
バランスの取れた文字列は再帰的データ型として定義すると自然に特徴付けられる:
文字列の集合 \(\text{RecMatch}\) を次の規則で再帰的に定義する:
-
: \(\lambda \in \text{RecMatch}\)
-
: \(s, t \in \text{RecMatch}\) なら、次の関係が成り立つ:
\[ {\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,} t \in \text{RecMatch} \]
この定義で使われている記号列 \({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,} t\) は本来ならば次のように書かれるべき文字列の連結を表す:
\[ {\color{red} \,\textbf{\textsf{[}}\,} \cdot ( s \cdot ( {\color{blue} \,\textbf{\textsf{]}}\,} \cdot t )) \]
これからは基本的に \(\cdot\) を省略して表記する。
この記法の例を示す。ベースケースから \(\lambda \in \text{RecMatch}\) が分かるので、構築ケースで \(s = t = \lambda\) とすれば次が分かる:
\[ {\color{red} \,\textbf{\textsf{[}}\,} \lambda {\color{blue} \,\textbf{\textsf{]}}\,} \lambda = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \in \text{RecMatch} \]
構築ケースをさらに適用すれば次も分かる:
\[ \begin{aligned} & {\color{red} \,\textbf{\textsf{[}}\,} \lambda {\color{blue} \,\textbf{\textsf{]}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \in \text{RecMatch} && (s = \lambda,\ \ t = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \text{ とした}) \\[3pt] & {\color{red} \,\textbf{\textsf{[}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \lambda = {\color{red} \,\textbf{\textsf{[}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \in \text{RecMatch} && (s = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,},\ \ t = \lambda \text{ とした}) \\[3pt] & {\color{red} \,\textbf{\textsf{[}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \in \text{RecMatch} && (s = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,},\ \ t = {\color{red} \,\textbf{\textsf{[}}\,} {\color{blue} \,\textbf{\textsf{]}}\,} \text{ とした}) \end{aligned} \]
括弧のバランスが取れているとき、開き括弧と閉じ括弧が同じ個数だけ存在するのは明らかである。再帰的データ型の扱いに慣れるために、この事実を再帰的な定義から注意深く証明してみよう。まず、文字列 \(s\) に含まれる文字 \(c \in A\) の個数を表す関数 \(\#_{c}(s)\) を定義する:
\(c \in A\) に対して、関数 \(\#_{c}(\lambda)\colon A^{\ast} \to \mathbb{N}\) を次の規則で再帰的に定義する:
:
\[ \#_{c}(\lambda) ::= 0 \]
:
\[ \#_{c}(\langle a, s \rangle) ::= \begin{cases} \#_{c}(s) & a \neq c \text{ のとき} \\[5pt] 1 + \#_{c}(s) & a = c \text{ のとき} \end{cases} \]
次の補題は定義 7.2.2に関する構造的帰納法から直ちに従う。詳細は練習問題 (問題 7.9) とする。
任意の文字列 \(s\), \(t\) で次の等式が成り立つ:
\[ \#_{c}(s \cdot t) = \#_{c}(s) + \#_{c}(t) \]
\(\text{RecMatch}\) に属する全ての文字列は開き括弧と閉じ括弧を同じ個数だけ持つ。
\(\text{RecMatch}\) の定義 (定義 7.2.1) に関する構造的帰納法で示す。文字列 \(s\) に関する次の述語 \(P(s)\) を帰納法の仮定とする:
\[ P(s) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(s) = \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(s) \]
: \(s = \lambda\) のとき、定義 7.2.2 のベースケースから次の関係が分かる:
\[ \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(\lambda) = 0 = \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(\lambda) \]
よって \(s = \lambda\) のとき \(P(s)\) は成り立つ。
: ある文字列 \(s\), \(t\) で \(P(s)\) と \(P(t)\) が成立すると仮定する。その上で \(P({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,} t)\) を示せばよい:
\[ \begin{aligned} \#_{{\color{red} \,\textbf{\textsf{[}}\,}}({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,} t) &= \#_{{\color{red} \,\textbf{\textsf{[}}\,}}({\color{red} \,\textbf{\textsf{[}}\,}) + \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(s) + \#_{{\color{red} \,\textbf{\textsf{[}}\,}}({\color{blue} \,\textbf{\textsf{]}}\,}) + \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(t) && (\text{補題 }\href{#lemma-7-2-3}{7.2.3}) \\[8pt] &= 1 + \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(s) + 0 + \#_{{\color{red} \,\textbf{\textsf{[}}\,}}(t) && (\#_{{\color{red} \,\textbf{\textsf{[}}\,}} の定義) \\[8pt] &= 1 + \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(s) + 0 + \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(t) && (P(s) \text{ と } P(t)) \\[8pt] &= \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}({\color{red} \,\textbf{\textsf{[}}\,}) + \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(s) + \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}({\color{blue} \,\textbf{\textsf{]}}\,}) + \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}(t) && (\#_{{\color{blue} \,\textbf{\textsf{]}}\,}} の定義) \\[8pt] &= \#_{{\color{blue} \,\textbf{\textsf{]}}\,}}({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,} t) && (\text{補題 }\href{#lemma-7-2-3}{7.2.3}) \end{aligned} \]
以上で構築ケースでも証明できた。よって構造的帰納法の原理より \(P(s)\) は全ての \(s \in \text{RecMatch}\) で成り立つ。 ■
注意: データ型の再帰的な定義において、同じ要素が異なる方法で構築できるとき、その定義は曖昧 (ambiguous) であると言う。定義 7.2.1 は曖昧でないように注意深く選んだものなので、その定義を使って定義される再帰的な関数は必ず well-defined となる。曖昧なデータ型の定義を使って再帰的な関数を定義すると、値が一意に定まらず実際には関数が定義できない場合が多い。この問題の例を示すために、括弧からなるバランスの取れた文字列の曖昧な定義を次に示す:
集合 \(\text{AmbRecMatch} \subseteq \left\{ {\color{blue} \,\textbf{\textsf{]}}\,}, {\color{red} \,\textbf{\textsf{[}}\,} \right\}^{\ast} \) を次の規則で再帰的に定義する:
-
: \(\lambda \in \text{AmbRecMatch}\)
-
: \(s, t \in \text{AmbRecMatch}\) のとき、\({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,}\) と \(st\) も \(\text{AmbRecMatch}\) に属する。
定義 7.2.4 が \(\text{RecMatch}\) の異なる定義であることは容易に分かる。言い換えれば \(\text{AmbRecMatch} = \text{RecMatch}\) は確かに成り立つ (問題 7.20)。また、\(\text{AmbRecMatch}\) の定義の方が間違いなく理解しやすい。しかし \(\text{RecMatch}\) の定義 (定義 7.1.1) と異なり \(\text{AmbRecMatch}\) の定義は曖昧なので、本節の他の部分で \(\text{AmbRecMatch}\) は使用しなかった。曖昧性から生じる問題の例を示そう。括弧からなるバランスの取れた文字列 \(s\) を \(\text{AmbRecMatch}\) の定義に従って構築するとき、適用される構築ケースの回数を \(f(s)\) と定義する。つまり、次のように \(f(s)\) を定める:
\[ \begin{aligned} \text{ベースケース: } && f(\lambda) &::= 0 \\ \text{構築ケース: } && f({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,}) &::= 1 + f(s) \\ && f(st) &::= 1 + f(s) + f(t) \end{aligned} \]
この定義の何が問題なのかと思ったかもしれない。しかし、少し考えると \(f(\lambda)\) の値が二つの値を持つことが分かる:
\[ \begin{aligned} 0 &= f(\lambda) && (f \text{ のベースケース}) \\ &= f(\lambda \cdot \lambda) && (\text{連結の定義のベースケース}) \\ &= 1 + f(\lambda) + f(\lambda) && (f \text{ の構築ケース}) \\ &= 1 + 0 + 0 && (f \text{ のベースケース}) \\ &= 1 \end{aligned} \]
これは数学的な関数の定義として全く望ましくない！