与えられた正規表現が何かにマッチするかどうかをチェック

Question

与えられた正規表現がどんな文字列にもマッチするかどうかチェックできますか？具体的には、私は、関数を探しています.f $regexがすべての文字列と一致する場合はtrueを返します。

これは、「正規表現を指定すると、rと一致しない文字列が存在しますか？私はこれが "すべての文字列"のセットに境界を置くことなく解けるとは思わない。つまり、文字列に "blahblah"が含まれていないと仮定すると、rが "blahblah"と一致するかどうかを単に確認できます。しかし、もしそのような境界がないならどうでしょうか？正規表現rが.*と等価であるかどうかをチェックすることで、この問題が解決できるかどうか疑問に思っています。

Answer 1

これはまさにあなたの質問に答えていませんが、簡単な答えはで来るのは難しいですなぜうまくいけば少し説明：

まず、用語「正規表現」は少し暗いです、これだけ明確にするために、我々

• 確定的有限オートマトン（DFAs）に相当する「厳密な」正規表現です。
• ルックアヘッド、バックレファレンスなどのようなベルとホイッスルを追加するPerl互換の正規表現（PCRE）。これらはPythonやJavaなどの他の言語でも実装されています。
• 実際のPerl正規表現は、?{...}構文を使用して、任意のPerlコードを含め、さらに狂ったようになります。

この問題は、厳密な正規表現では解決できると思います。対応するDFAを作成し、そのグラフを検索して、非受諾状態へのパスがあるかどうかを確認します。しかし、これは通常、PCREである '実世界'の正規表現には役立ちません。

私はPCREがチューリング完全ではないと思っています（わかりませんが、この質問も参照してください：Are Perl regexes turing complete?）。もしそうなら、私はJim Garrisonがコメントしたように、これは基本的に停止問題です。 しかし、上記の方法を役に立たないものにするために、それらをDFAに変換することは容易ではありません...

私はPCREの回答はありませんが、上記の構文（後方参照など）それはかなり難しいだろう、私は想像しています。私は「不可能」と言っています。

本物のPerl正規表現?{...}は、確かにチューリングが完了しているので、ドラゴンズがあります。あなたは運が悪いと思います。