fixedpoint.jp - 1 alphabetについての正規表現が任意の文字列にマッチするかどうかの判定はNP-hard




1 alphabetについての正規表現が任意の文字列にマッチするかどうかの判定はNP-hard

プログラミングで正規表現というと様々な実装がありますが、元々は正規言語として定義されています。この元々の正規言語にはsubmatch captureといった構文はありません。

同じalphabetに対する2つの正規表現が同じ言語を定義する(つまり、マッチする文字列の集合が同じ)かどうかの判定がNP-hardであることは昔から知られていますが、実際にはこれより強い主張が成り立ちます: {a}という1つのalphabetだけについての正規表現が、a*という正規表現と同じ言語を定義するかどうかの判定もNP-hardです。これを証明している論文では、3-SATの充足可能性判定を上の判定に還元しています。

というわけで、与えられた正規表現が任意のaの有限列にマッチするような"つまらない"ものかどうかを判定するのさえ意外(?)と難しいです。

参考


© 2006-2017 fixedpoint.jp