一部の入力文字列に対して、一致するものを永久に検索する正規表現はありますか？
1789 次
8 に答える
33
有限入力の場合、停止しない正式な正規表現はありません。
正式な正規表現は、決定性有限オートマトンに変換できます。DFAは、一度に1文字ずつ入力を読み取り、入力の最後に、受け入れ状態または非受け入れ状態のいずれかになります。状態が受け入れている場合、入力は正規表現と一致します。そうでなければ、そうではありません。
現在、ほとんどの「正規表現」ライブラリは、後方参照など、正規表現ではないものをサポートしています。これらの機能を避け、有限の入力がある限り、停止が保証されます。そうしないと...使用しているものによっては、停止が保証されない場合があります。たとえば、Perlでは任意のコードを挿入できますが、チューリングマシンに相当する任意のコードが停止することは保証されていません。
ここで、入力が無限大の場合、停止することのない簡単な正規表現を見つけることができます。たとえば、「.*」。
于 2009-08-06T20:48:46.490 に答える
7
正式な正規表現は、実際には、文字列を解析するための決定性有限オートマトンを記述する方法です。入力の最後にDFAが受け入れ状態になると、正規表現は「一致」します。DFAは入力を順番に読み取るため、入力の最後に達すると常に停止します。一致するかどうかは、DFAのどの状態で停止するかを調べるだけです。
サブストリングのマッチングは事実上同じですが、ストリングの1回のリードスルーの終了時に強制的に停止する代わりに、DFAは、可能な各サブストリングを1回読み取った後に強制的に停止することになります。（はい、ほとんどの正規表現エンジンは、DFAですべての可能なサブストリングをスローするよりも少し最適化された方法でこれを実装しますが、概念的には制限がまだあります）。
したがって、DFAが停止しない可能性がある唯一のケースは、入力が無限大である場合です。これは、一般に、停止問題の範囲を超えていると見なされます。
于 2009-08-06T20:46:27.900 に答える
2
止まらない正規表現を見つけることはできないと思います。
入力のサイズは有限です。正規表現の一致するサブグループの最大サイズは、最大で入力のサイズです。
使用されているアルゴリズムがかなり愚かでない限り（ケースを複数回調べる）、一致するサブグループの数も有限になります。
だから、それは停止します。
于 2009-08-06T20:38:35.373 に答える
1
この質問によると、すべての正規表現は停止します。
于 2009-08-06T20:38:20.193 に答える
0
無限に長い文字列は永久に解析されますが、永久に解析される入力文字列を想像することはできません。正規表現は、潜在的に無限の単語のセットである正規言語を記述できるとすると、正規表現は、無限の長さの単語を含む、無限の単語の言語を記述できます。ただし、入力文字列を無限に長くすることはできないため、ある時点で停止する必要があります。
たとえば、a * bがその言語で受け入れられ、「a」の文字列が無限に長い場合、そうです、正規表現は停止しません。しかし実際には、これは不可能です。
于 2009-08-06T20:41:45.257 に答える
0
はい。
正規表現は、有限状態マシンで表すことができます。アトミック入力を受け取るたびに、明確に定義されたFSMが既知の状態に遷移します。
例外は、入力が無限である場合ですが、これは有限の入力を処理するため、停止問題には適用できません。有限状態マシンと有限入力がある場合、マシンが停止するかどうかを常に判断できます。
于 2009-08-06T21:00:00.557 に答える
0
ダニエルの答えの+1：すべての有限入力により、真の正規表現（つまり、後方参照やその他の非正規表現なし）が停止し、正規表現はDFAと同等です。
おまけ: 正規表現のマッチングはシンプルかつ高速です (ただし、Java、Perl、PHP、Python、Ruby などでは低速です)。
http://swtch.com/~rsc/regexp/regexp1.html
この記事の上部にある 2 つのグラフは、y 軸のスケールが異なることに注意してください。1 つは秒、もう 1 つはマイクロ秒です。
于 2010-05-13T17:45:29.643 に答える