「正規表現の積」に関する考察

元問題はこちらです。

i-i.hatenablog.jp

準備

用語の定義

一般的な形式言語の用語

  • アルファベットΣ は、文字列に含まれてよい文字の集合のことです。元問題では小文字ラテンアルファベット26文字ですが、一般化しておきます。
  • 言語とは、文字列の集合のことです。以下の話では、言語はすべて無限集合です（これは扱う問題の性質によるものです）。議論の展開によっては普通に「文字列の集合」と書いてある部分もありますが、意味は同じです。

マッチする という言葉の意味について、念のため

  • 正規表現が 文字列全体にマッチ は、C++のstd::regex_match動作のことを言うことにします。正規表現の前に^、後ろに$がついている状況を考えるとわかりやすいです。
  • 正規表現が 文字列の一部にマッチ は、C++のstd::regex_search動作のことを言うことにします。形式的には、正規表現の前後に.*を付け加えてできる正規表現がその文字列 全体にマッチ することと等価です。

この問題に特殊化された用語（方言）

  • 正規表現 は、アルファベット・.・*・|から構成される文字列とします。.は任意のアルファベット一文字にマッチ、*はクリーネ閉包、|は選言と解釈され、エスケープは必要ありません（基本正規表現の動作と同じです）。クリーネ閉包は、アルファベットまたは.にのみ適用できます（かっこがないため文字列への適用ができません）。

    • この定義は、通常の意味での正規表現からかけ離れたものになっています。通常の意味での正規表現との違いについて論じるときには、「真の正規表現」という言葉を使うことで区別します。

  • 正規表現rが文字列の集合Sを 認識する とは、Sに含まれるすべての文字列sについて、正規表現rは文字列sの 一部にマッチ し、Sに含まれないすべての文字列sについて、正規表現rは文字列sの 一部にマッチ しないことを言います。

定義に使うのは 全体にマッチ ではありません。この定義のもと、 正規表現 は、真の正規表現より記述力が低いです。例えば、「aを含まない文字列」という言語を記述できません。

問題の形式的定義

正規表現Aと正規表現Bが与えられる。ただし、正規表現Aと正規表現Bには*と|は含まれない（.は含まれうる）。次の条件を満たす文字列sの集合をSとする。

「正規表現Aは文字列sの 一部にマッチ する。かつ、正規表現Bは文字列sの 一部にマッチ する。」

このようなSを認識する正規表現rに含まれる選言演算子（|）の最小個数を求めよ。

AにもBにも含まれないアルファベットの要素があることを仮定してもよい。

元問題との対応

  • アルファベットはΣ = { 'a', 'b', 'c', ..., 'z' }の26文字からなる集合である。
  • 問題は以下の形式で入力される。ここで、AとBの末尾には改行文字がつく（Bの後に改行がつくかは明示されていないが）。
A
B
  • 出力は十進数で（明示されていないが）。
  • Aの長さ|A|とBの長さ|B|はそれぞれ1以上10以内であるとき、これを2秒以内に解けるアルゴリズムを構成せよ。ただし、メモリ制約は512MBとする。

考察

Sを認識する正規表現は必ず存在する

あまり形式的ではありませんが、そのような正規表現を構成することは可能です。例として、A=b.a.、B=.a.bの場合（サンプルケース4）を考えます。

b . a .
. a . b b.a..*.a.b
. a . b b.a.a.b
. a . b b.aa.b
. a . b b.a.b
. a . b baab
. a . b NG
. a . b .abba.
. a . b .a.b.a.
. a . b .a.b.*b.a.

こうして出てくる単正規表現をすべてつなげたb.a..*.a.b|b.a.a.b|b.aa.b|b.a.b|baab|.abba.|.a.b.a.|.a.b.*b.a.はSを認識する正規表現になります。

このような方法で、|A|+|B|+1個の単正規表現の選言である、高々|A|+|B|個しか選言演算子を含まない、Sを認識する正規表現を構成することは常に可能です。

もちろん、サンプルケース4の解説を見ればわかるように、この方法で構成した正規表現は選言演算子最小性を満たすとは限りません。

この方法で出てくる単正規表現を、 基本解 と呼ぶことにします。

a*のようなアルファベットの要素に対するクリーネ閉包も活用されるはず

サンプルケースにはそのような例はありませんが、A=baa、B=aabの時、Sを認識する正規表現としてbaa.*aab|baaa*b|aabaa|aab.*baaを選べば必要な選言演算子は最小の3つになるはずです。この時、a*を含まない正規表現では必要な選言演算子の数が多くなるはずです。

このような場合、複数の単正規表現がマッチする部分を持つような文字列（例えばbaaaabにはbaa.*aabにマッチする部分もあるし、baaa*bにマッチする部分もある）があることが事態を複雑化させている原因でしょう。

選言演算子の最小化をするのは困難な問題のように思えます。排他的選言ではなく普通の選言になっていることが原因でしょう。

この手の、xorなら簡単だがorだと困難という問題はいくつかあります。

  • xor-SATはPですが、SATはNP完全です。
  • DFAやNXAの状態数最小化はPですが、NFAの状態数最小化はPSPACE完全です。ここで、DFAは決定性有限状態オートマトン(Deterministic Finite Automaton)、NFAは非決定性有限状態オートマトン(Nondeterministic Finite Automaton)であり、NXA (Nondeterministic Xor Automaton)は、NFAで暗黙に使われているor演算をxorに置き換えたものです。

二番目の話は、d.y.d.の2010/12/13の記事で知りました。

選言演算子最小化は、論理式最小化に似た雰囲気がありますし、NFAの状態数最小化に似た雰囲気もあります。そのため、入力文字列長の多項式時間で解くのは困難かもしれません（論理式最小化は判定版がNP完全になる問題だったはずです）。

Open problem

基本解以外を使って選言演算子の数を減らせる場合

先ほど示したA=baa、B=aabの例は、基本解としては出てこない単正規表現baaa*bを使うことで選言演算子を減らすことができる場合です。

実験してみると、基本解に適当に以下の操作を施してできる単正規表現は有効利用できる場合があることがわかります。

  • aをaa*に変換する（実際に選言演算子を減らす役に立つのはaをa*に変換する手続きだけ？）

そのようにして作ることができる単正規表現を、 派生解 と呼ぶことにします（基本解も派生解に含まれます。また、派生解の中にはSに含まれない文字列の一部分にマッチしてしまう単正規表現も含まれます）。

【予想】単正規表現として派生解以外は有用ではない

形式的に書くと以下のような意味です。

単正規表現rが 有用でない とは、以下の条件のいずれかを満たすことを言います。

  • 単正規表現rは、Sに含まれない文字列の一部分にマッチする。
  • 以下の条件を満たす派生解r'が存在する。

第一の条件に当てはまる場合明らかにSを認識する正規表現に含まれませんし、第二の条件に当てはまる場合はrの代わりにr'を使ってもSを認識する正規表現となります。

これは、派生解以外の単正規表現を用いても、派生解のみ用いた場合に比べ選言演算子を減らすことはできない、という主張より強い主張です。

クリーネスター演算子の出現回数

基本解においてクリーネスターは中央にしか出てきません。これ以外のところにクリーネスターを使うことは意味がないように思われます。

【予想】クリーネスター演算子を二回以上使った単正規表現は有用ではない

先ほど示した例において、派生解であるbaaa*bの代わりにba*b*aabという派生解でない単正規表現を使っても選言演算子を減らすことができますが、これが認識する言語はbaaa*bが認識する言語の真部分集合であり、有用ではありません。

余談

正規表現 は多くの言語演算上で閉じている

真の正規表現よりも表現力が低いことは説明しました。まず、言語演算が閉じているかを確認してみます。

  • 選言
    • 間に|を挟んで連結した正規表現で認識できる。
  • 連言
    • 認識する正規表現は、基本解の構築と類似の手順で構成できる。
  • クリーネスター
    • 空正規表現で認識できる。正規表現の0回の繰り返しは空正規表現であり、それは任意の文字列の一部分にマッチする、つまり、その言語はΣ*（すべての文字列からなる集合）である点に注意したい。
  • 連接
    • 単正規表現同士なら、間に.*を挟んで連結した単正規表現で認識できる。単正規表現でない場合でも、各構成単正規表現の順序対全てについて同様にしたものの選言として構成できる。
  • 鏡像
    • .*やa*を仮想的に"一文字"とみなして、"一文字"ずつ逆順にした正規表現で認識できる。
  • 否定
    • 閉じていないどころか一切書けない。

クリーネスターは退化しているので実質使えないことになります。表現力は、真の正規言語より真に弱いstar-free言語よりさらに真に弱いものになります。 クリーネスター演算子はstar-free正規表現では使えませんが、一文字へのクリーネスター演算子は補集合演算で作り出すことができます。実際、.*は \emptyset^ c（空集合の補集合）として書けます。また、a*は (\emptyset^ c \lbrack\hat{}a\rbrack \emptyset^ c)^ c（a以外の文字を何か一文字は含む文字列全体以外からなる集合）として表せます。 star-free正規表現だと書けるが正規表現で書けない言語には、「aを含まない文字列すべての集合」などがあります（ (\emptyset^ c a \emptyset^ c)^ cのようにstar-free正規表現で書けます）。ちなみに真の正規表現だと書けるがstar-free正規表現で書けない言語には、「aを偶数回繰り返した文字列すべての集合」などがあります。