Halten alle regulären Ausdrücke an?

Question

Gibt es einen regulären Ausdruck, der für eine Eingabezeichenfolge immer nach einer Übereinstimmung sucht?

Answer 1

Für eine endliche Eingabe gibt es keinen formellen regulären Ausdruck, der nicht anhalten kann.

Jeder formale reguläre Ausdruck kann in eine Deterministische Finite Automata übersetzt werden. Ein DFA liest die Eingabe ein Zeichen gleichzeitig, und am Ende der Eingabe befinden Sie sich entweder in einem akzeptierenden Zustand oder in einem nicht akzeptierenden Zustand. Wenn der Status akzeptiert wird, stimmt die Eingabe mit dem regulären Ausdruck überein. Sonst nicht.

Jetzt unterstützen die meisten "Regular Expression" -Bibliotheken Dinge, die keine regulären Ausdrücke sind, wie z. B. Rückverweise.Solange Sie sich von diesen Merkmalen fernhalten und eine endliche Eingabe haben, ist Ihnen ein Halt garantiert. Wenn Sie nicht ... abhängig davon, was Sie gerade verwenden, können Sie nicht garantiert ein Halt sein. Perl erlaubt zum Beispiel das Einfügen von beliebigem Code und willkürlicher, turing-machine-äquivalenter Code wird nicht garantiert gestoppt.

Nun, wenn die Eingabe unendlich ist, dann können triviale reguläre Ausdrücke gefunden werden, die niemals anhalten. Zum Beispiel ".*".

Answer 2

Nicht in dem Sinne, den Sie beschreiben, können Sie einige sehr ineffiziente reguläre Ausdrücke haben, die eine Menge Ressourcen verbrauchen und am Ende die Regex-Engine töten, das ist nicht das Gleiche wie anhalten.

Ich glaube nicht, dass das Anhalten hier wirklich zutrifft, wie die anderen Kommentatoren dieses Posts so geschickt gezeigt haben. http://en.wikipedia.org/wiki/Halting_problem

Answer 3

Nach this question, hält jeder regulären Ausdruck.

Answer 4

Ich stelle mir vor, es ist nicht möglich, einen regulären Ausdruck zu finden, der nicht anhält.

Die Größe Ihrer Eingabe ist endlich. Die maximale Größe jeder übereinstimmenden Untergruppe des regulären Ausdrucks entspricht maximal der Größe Ihrer Eingabe.

Wenn der Algorithmus, der verwendet wird, ziemlich dumm ist (Fälle mehrfach durchlaufen), wird auch die Anzahl der übereinstimmenden Untergruppen endlich sein.

So wird es anhalten.

Answer 5

Ich kann mir eine Eingabezeichenfolge nicht vorstellen, die für immer analysiert würde, obwohl eine unendlich lange Zeichenfolge für immer geparst würde. Da ein regulärer Ausdruck eine reguläre Sprache beschreiben kann, bei der es sich möglicherweise um eine unendliche Menge von Wörtern handelt, kann ein Regex eine Sprache unendlicher Wörter beschreiben, einschließlich Wörtern unendlicher Länge. Jedoch kann keine Eingabe-Zeichenkette unendlich lang sein, so dass sie irgendwann anhalten müsste.

Wenn zum Beispiel a * b in der Sprache akzeptiert wird und Sie eine unendlich lange Folge von 'a's haben, dann würde ja die Regex niemals anhalten. In der Praxis ist dies jedoch unmöglich.

Answer 6

Formale Regex ist eigentlich eine Methode zur Beschreibung eines deterministischen endlichen Automaten zum Analysieren von Strings. Die Regex "passt", wenn der DFA am Ende der Eingabe in einen akzeptierenden Zustand übergeht. Da das DFA seine Eingabe sequenziell liest, wird es immer angehalten, wenn es das Ende der Eingabe erreicht, und ob es eine Übereinstimmung gibt oder nicht, ist lediglich eine Frage der Untersuchung, in welchem ​​Zustand des DFA es anhält.

Der Substring-Abgleich ist effektiv derselbe, außer dass der DFA nicht gezwungen wird, am Ende eines Lesevorgangs der Zeichenfolge anzuhalten, sondern nach dem Lesen jeder möglichen Teilzeichenkette angehalten wird - immer noch ein endlicher Fall. (Ja, die meisten Regex-Engines implementieren dies in einer etwas optimierteren Weise, als nur jeden möglichen Teilstring bei einem DFA zu werfen - aber konzeptionell ist das Limit immer noch da).

Daher ist der einzige mögliche Fall, in dem das DFA nicht anhalten würde, wenn die Eingabe unendlich wäre, was im Allgemeinen als nicht im Bereich des Halteproblems liegend angesehen wird.

Answer 7

Ja.

Ein regulärer Ausdruck kann durch eine endliche Zustandsmaschine dargestellt werden. Jedes Mal, wenn Sie eine atomare Eingabe erhalten, wird jede gut definierte FSM in einen bekannten Zustand übergehen.

Die Ausnahme ist, wenn Sie unendlich Eingang haben, aber dies ist nicht für das Halteproblem anwendbar, da es sich um endliche Eingabe handelt. Wenn Sie eine endliche Zustandsmaschine und endliche Eingabe haben, ist es immer möglich zu bestimmen, ob Ihre Maschine anhalten wird oder nicht.

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

Answer 8

+1 für Daniel Antwort: Alle Eingänge finite verursachen wahre regex ist (d.h. ohne Rückreferenzierungen oder andere nicht-regulären Ausdruck Funktionen) zu stoppen, und regex'S sind auf DFAs äquivalent.

Bonus: Regular Expression Matching kann einfach und schnell (aber in Java, Perl, PHP, Python, Ruby, ... langsam ist)

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

Beachten Sie, dass die beiden Graphen bei der Anfang des Artikels haben unterschiedliche Maßstäbe auf der Y-Achse: eins ist Sekunden, das andere ist Mikrosekunden!