与えられた正規表現がどんな文字列にもマッチするかどうかを確実に判断できますか？

ユーザー入力の正規表現を使用して、それが任意の文字列と一致するかどうか、つまり.+または.*に「減らす」かどうかを判断したいとしますか？与えられた正規表現がどんな文字列にもマッチするかどうかを確実に判断できますか？

私はthis exists以来、私の質問が停止問題になるとは思っていますが、私は本当に間違っていると思います。

2013-05-24 Alex S

理論上、Kleene Starまたは '*'は技術的に無限大ですが、あなたが '*'を使って32767回まで繰り返しテストを投稿したモジュールです。 – squiguy

入力が空白/空/ヌル/長さゼロでないかどうかをチェックするのはどうですか？他の条件がないので、ユーザーの入力はあなたの要件と一致する必要があります。 –

@Burhan Khalidあなたは疑問を誤解しています。彼は任意の正規表現が任意の文字列にマッチするかどうかをテストしたい。 – Patashu

私はあなたが望むとは思わないが、正規表現の文法からHaltingの問題に似ています。アルファベットとオートマトンで認識される言語が有限であることを考慮すると、あなたの言語のあらゆる世界を試し、正規表現がそれを認識できるかどうかをテストするダミーアルゴリズムを使用することができます。

実際には、このメソッドは非常に複雑ですが、入力の数が列挙可能であるため、Haltingの問題ではない「未定義」状態はありません。

このダミーアルゴリズムのより良いバージョンが存在するかどうかは実際にはわかりませんが、私はHaltingの問題との類似性に関するあなたの質問に答えることを願っています。

2013-05-24 06:21:15 ibi0tux

私はそれが停止問題に変わるかもしれないと思った理由は、私がリンクしたモジュールのようなテクニックを使うよりも、正規表現を分析する良い方法がないだろうと推測しました。それが事実だったなら、問題は「このユニークな文字列のリストは無限ですか？既知の単語に対するテストでは十分ではありません。 –

答えて