後方参照付き正規表現が表す言語は必ずしも正規言語ではない

バイト先の勉強会で何か発表してよと言われたので、オートマトンの基礎（有限オートマトンと正規言語）について扱ったのだが、僕がオートマトンと形式言語の授業を取ったのは学部 2 年の頃なので、細かい部分についてはかなり忘れていた¹。スライド作りのために計算理論の基礎 [原著第 3 版] 1.オートマトンと言語 を引っ張り出して勉強し直しているので、しばらくはこの分野で面白いトピックがあれば、紹介しようと思う²。 今回は、有名な事実ではあるが、後方参照を認める正規表現が表す言語は正規言語とは限らないことを示す。

後方参照

後方参照とは、キャプチャグループにマッチした文字列を、後続のパターンの中で再び参照する機能である。後方参照を含む正規表現の例を以下に示す。

^(.)o\1$

キャプチャグループ(.)は任意の 1 文字にマッチし、その文字をグループ 1 としてキャプチャする。次に文字oがマッチし、その後にグループ 1 でキャプチャされた文字列が\1によって再びマッチする。すなわち、この正規表現は同じ文字がoの前後にある文字列にマッチする。 例えば、sos³やcoc⁴、bob⁵などの文字列が該当する。

具体的な使い方として、簡易的に HTML タグの対応のチェックが考えられる。

<([A-Za-z][A-Za-z0-9]*)\b[^>]*>.*?</\1>

もちろん厳密な仕様に沿った HTML タグの検査はさらに複雑だが、最低限、開始タグと終了タグが同じであることを確認できる。

正規言語

正規言語とは、ある有限オートマトンで認識できる言語である。たとえば、以下の有限オートマトンは 0 と 1 からなるアルファベット上の文字列のうち、すべての文字が 0 である非空文字列、またはすべての文字が 1 である非空文字列を受理する。

したがって、そのような文字列の集合（= 言語）は正規言語であると言える。このような正規言語を表現するための手法として、正規表現がある。これは、$\cup$（和集合）、$*$（スター演算）、$\circ$（連結）によって正規言語を表現することができる⁶。たとえば、上の有限オートマトンと等価な正規表現を以下に示す。

正規表現 $R$ で表現できる言語 $L$ は常に正規言語である。すなわち、後方参照付き正規表現が表現できる言語に、正規言語でないものが含まれていればタイトルの命題を証明することができる。

まず、最初に示した後方参照を含む正規表現を見てみよう。

^(.)o\1$

これはアルファベットの個数によって状態数は増えていくものの、有限オートマトンで表現できることがわかる。たとえば、アルファベット $\Sigma = \{o, p\}$ であるとすると、以下の有限オートマトンで表現できる。

一方、次のような後方参照付きの正規表現は有限オートマトンでは表現できない。

^(a*)b\1$

直感的には 1 つ目のキャプチャグループでキャプチャされる文字列長を保存しておく手段が有限オートマトンには存在せず、有限状態に落とせないからである。 しかし、残念ながら直感的に無限状態が必要そうに見えても有限オートマトンで表現できる言語も存在する。たとえば、「文字列中に登場する $01$ の個数と $10$ の個数が一致する文字列」による言語である。これを有限オートマトンで表現する方法は読者への課題とするが、直感的に正規言語であるかどうかを区別することは難しい。

ある言語が正規言語であるかどうかを証明する道具として、ポンピング補題がよく使われる。

ポンピング補題

正規言語 $L$ に属する文字列 $s = s_1s_2s_3\dots s_n$ を考える。$L$ を認識する有限オートマトン $A$ の状態数を $p$ として、$L$ 上の文字列長 $n$ は $p$ 以上であると仮定する。 すると、文字列 $s$ が $A$ 上を遷移するときの状態列は以下のようになる。

状態列の長さは $n+1$ であるが、$n \ge p$ より、$n + 1 \gt p$ である。 したがって、鳩の巣原理より状態列の中に必ず同じ状態が最低でも 2 回は現れる。たとえば $n = p = 4$ とすると、以下のような状態列が考えられる。

ここで、$s$ を 3 つの文字列 $x, y, z$ に分割する。まず、$x$ は重複する状態に到達するまでの文字列、すなわちここでは $x = s_1$ である。次に、$y$ は重複する状態に再度到達するまでの文字列、すなわち $y = s_2s_3$ である。最後に、$z$ は残りの文字列、$z = s_4$ である。このように分割すると、以下のような擬似的な有限オートマトンを考えることができる。

すると、この有限オートマトンは $s = xyz$ だけでなく、$xz$ や $xyyz$、$xyyyyyz$ のような、$y$ を 0 回以上繰り返した文字列 $xy^i z \;\; (i \ge 0)$ も受理することがわかる。このように、任意の正規言語は、ある長さ $p$ が存在し、長さが $p$ 以上のある任意の文字列 $s$ を、任意の $i \ge 0$ について $xy^i z$ を受理するように、$s = xyz$ に分割できる。 また、重複する状態を最初の $p$ 文字を読むまでの範囲から選んでいるため、$|xy| \le p$ である。さらに、2 回現れる状態は異なる位置で現れるので、$|y| > 0$ である。

これを主張する補題がポンピング補題である。

証明

では、最後に後方参照付き正規表現が表す言語が必ずしも正規言語でないことを、ポンピング補題を用いて証明する。

$A$ を言語 $\{a^n b a^n \mid n \ge 0\}$ とする。$A$ が正規言語であると仮定する。

$p$ をポンピング長とする。また、文字列 $s = a^p b a^p$ をとる。$s$ は $A$ の要素で長さは $p$ 以上であるから、ポンピング補題により $s$ は 3 つの部分文字列 $s = xyz$ に分割できる。 加えて、任意の $i \ge 0$ について文字列 $xy^i z$ は $A$ に属し、$|y| \gt 0$ と $|xy| \le p$ を満たす。

ここで、$|xy| \le p$ であるから、$x$ と $y$ は $s = a^p b a^p$ の最初の $a^p$ に含まれる。さらに、$|y| > 0$ より、ある $j > 0$ を用いて、$y = a^j$ と書ける。

1. $y = a^j$ のとき、文字列 $xyyz = a^{p+j} b a^p$ となり、$p+j \neq p$ から $A$ の要素ではない。よってポンピング補題の 1 つ目の条件を満たさず、矛盾。

$A$ を正規言語と仮定すると矛盾するので、$A$ は正規言語ではない。

おすすめの曲 紹介コーナー