正規表現はすべて停止しますか？

Question

一部の入力文字列で一致を永久に検索する正規表現はありますか？

Answer 1

有限の入力の場合、停止しない正式な正規表現はありません。

正式な正規表現は、確定的有限オートマトンに変換できます。 DFAは一度に1文字ずつ入力を読み取り、入力の最後には受諾状態または非受諾状態のいずれかになっています。状態が受け入れられている場合、入力は正規表現に一致します。そうでなければ、それはしません。

ほとんどの「正規表現」ライブラリは、後方参照などの正規表現ではないものをサポートしています。あなたがそれらの機能から離れて、有限の入力を持っている限り、あなたは停止を保証されます。あなたがしていない場合...あなたが使っているものによっては、停止が保証されないこともあります。 Perlでは任意のコードを挿入することができ、任意のturing-machineと同等のコードは停止することが保証されていません。

入力が無限であれば、決して停止しない簡単な正規表現を見つけることができます。たとえば、「.*」と入力します。

Answer 2

あなたが記述している意味ではありませんが、リソースの大部分を占有し、正規表現エンジンを終了させる非常に非効率な正規表現を持つことができます。これは停止と同じではありません。

この投稿の他のコメント投稿者が非常に慎重に指摘しているので、私はここで実際に停止するとは思わないと思います。 http://en.wikipedia.org/wiki/Halting_problem

Answer 3

this questionによれば、すべての正規表現は停止します。

Answer 4

私は、停止しない正規表現を見つけることはできません。

入力のサイズは有限です。マッチした正規表現のサブグループの最大サイズは、最大で入力のサイズです。

使用されているアルゴリズムがかなりばかげている（複数回に渡って）場合、一致するサブグループの数も有限である。

これで停止します。

Answer 5

無限に長い文字列は永遠に解析されますが、永遠に解析される入力文字列は想像できません。正規表現は、潜在的に無限の単語の集合である通常の言語を記述できるとすれば、正規表現は、無限の長さの単語を含む無限の単語の言語を記述することができる。しかし、入力文字列は無限に長くなることはありません。したがって、ある時点では停止する必要があります。

たとえば、a * bが言語で受け入れられ、無限に長い文字列 'a'、thenがある場合、正規表現は決して停止しません。実際には、これは不可能です。

Answer 6

形式正規表現は、実際には文字列を解析するための確定的な有限オートマトンを記述する方法です。正規表現は、入力の最後にDFAが受け入れ状態になると "一致"します。 DFAは入力を順次読み込むので、入力の終わりに達すると常に停止し、一致するかどうかはDFAのどの状態が停止しているかを調べることに過ぎません。

文字列の1つのリードスルーの終わりで強制的に停止するのではなく、DFAが各可能な部分文字列を1回読み込んだ後に強制的に強制されます（有限の場合もあります）。 （はい、ほとんどの正規表現エンジンは、DFAで可能なすべての部分文字列を投げるだけではなく、少しでも最適化された方法でこれを実装していますが、概念的にはそこにはまだ限界があります）。

したがって、DFAが停止しない唯一の可能性のあるケースは、入力が無限である場合です。これは一般的に停止問題の範囲を超えて考えられています。

Answer 7

はい。

正規表現は、有限状態マシンで表現できます。原子入力を受け取るたびに、明確に定義されたFSMが既知の状態に遷移します。

無限の入力がある場合は例外ですが、有限の入力を処理するため、停止問題には適用できません。有限状態マシンと有限入力を持つ場合、マシンが停止するかどうかを常に判断することができます。ダニエルの答えのための

http://en.wikipedia.org/wiki/Finite_state_machine

Answer 8

1：すべての有限の入力が真の正規表現の（すなわち、後方参照または他の非正規表現の機能なし）停止するように引き起こし、正規表現のはのDFAに相当します。

ボーナス：正規表現のマッチングが 簡単かつ迅速することができます（が、JavaやPerl、PHP、PythonやRubyの、で遅いです...）

http://swtch.com/~rsc/regexp/regexp1.html

注2つのグラフこと記事の上部には、y軸上で異なる縮尺があります.1つは秒、もう1つはマイクロ秒です！