名前が示すように、正規表現は正規言語にのみ一致すると考えるかもしれません。しかし、実際に使用する正規表現には、理論上の表現で実装できるかどうかわからないものが含まれています。たとえば、後方参照をどのようにシミュレートしますか？そこで、疑問が生じます。実際に使用する正規表現の理論上の力は何ですか？一致させる方法を考えられます{(a^n)(b^n)|n>=0}か？どう{(a^n)(b^n)(c^n)|n>=0}ですか？
2157 次
2 に答える
7
あなたの質問に対する答えは、後方参照を許可する「正規表現」言語は、正規でも文脈自由でもないということです。（言い換えれば、あなたが指摘したように、正規言語でもCFLでも後方参照をシミュレートすることはできません。）実際、ウィキペディアは、私たちが実際に使用する「正規表現」言語の多くはNP-Completeであると言います。
多数の最新ツールでサポートされているように、無制限の数の後方参照とのパターンマッチングは、NP完全です（
[11]定理6.2を参照）。
他の人が示唆しているように、コンピュータ言語やライブラリで一般的にサポートされている正規表現言語は、形式言語理論の正規表現とは異なる動物です。Larry Wallは、Perlの「正規表現」に関して書いています。
「正規表現」[...]は、実際の正規表現にわずかに関連しているだけです。それでも、この用語はパターンマッチングエンジンの機能によって成長したため、ここでは言語の必要性と戦うつもりはありません。ただし、一般的には「正規表現」と呼びます。
あなたは尋ねました、
{（a ^ n）（b ^ n）| n> = 0}に一致させる方法を考えられますか？{（a ^ n）（b ^ n）（c ^ n）| n> = 0}はどうですか？
ここで、理論上の正規表現言語が「正方形の言語」と一致するかどうかをテストしようとしているのか、それとも（実用的な）正規表現言語での実装を探しているのかはわかりません。前者が不可能な理由は次のとおりです。これが、Java正規表現に対する後者の長い説明と実装です。
于 2010-09-28T20:24:22.037 に答える
4
あなたがほのめかしている正規表現の基本的な難しさは、正規表現には「記憶」がないという事実です。最も純粋な形式では、実際の正規表現はこれらの言語のいずれかを認識できないはずです。これらの種類の言語を解析できる正規表現は、定義上、正規表現ではありません。「私たちが使用する正規表現は練習です」とは、技術的には正規表現ではない拡張正規表現のことだと思います。
あなたの質問の問題は、あなたが特別に考案された理論的シナリオを実際の状況に適用しようとしているということです。それはほとんど常に災害で終わります。
ですから、私の答えは一種の非答えです。つまり、答えを得るには、拡張正規表現について質問するために質問を言い換える必要があると言っています。
この問題に役立つ可能性のあるいくつかのリソース：
私はまた、この考え方に貢献したい人のために、私の答えをコミュニティwikiにしています。
于 2010-09-27T17:06:31.647 に答える