Gegenseitig exklusive reguläre Ausdrücke

Question

Wenn ich eine Liste von regulären Ausdrücken habe, gibt es eine einfache Möglichkeit festzustellen, dass keine von beiden eine Übereinstimmung für dieselbe Zeichenfolge zurückgibt?

Das heißt, die Liste ist gültig, wenn und nur dann, wenn für alle Strings maximal ein Element in der Liste wird die gesamte Zeichenfolge übereinstimmen.

Es scheint, wie dies sehr schwierig sein wird (vielleicht unmöglich?) Endgültig zu beweisen, aber ich kann keine Arbeiten zu diesem Thema zu finden scheinen.

Der Grund, warum ich frage, ist, dass ich an einem Tokenizer arbeite, der Regex akzeptiert, und ich möchte sicherstellen, dass immer nur ein Token dem Kopf der Eingabe entsprechen kann.

Answer 1

Wenn Sie mit reinen regulären Ausdrücken (keine Rückreferenzierungen oder andere Merkmale, die sie verursachen kontextfreie oder kompliziertere Sprachen erkennen) arbeiten, was Sie fragen, ist möglich. Sie können jeden Regex in einen DFA konvertieren und dann (da reguläre Sprachen unter Kreuzungen geschlossen sind) diese zu einem DFA kombinieren, der den Schnittpunkt der beiden Sprachen erkennt. Wenn dieser DFA über einen Pfad vom Startstatus in einen akzeptierenden Status verfügt, wird dieser String von beiden Eingabe-Regexen akzeptiert.

Das Problem dabei ist, dass der erste Schritt der üblichen Regex-> DFA-Algorithmus zu konvertieren Sie die Regex zu einem NFA, dann konvertieren Sie die NFA zu einem DFA. Aber dieser letzte Schritt kann zu einem exponentiellen Anstieg in der Anzahl der DFA-Zustände führen, so dass dies für sehr einfache reguläre Ausdrücke nur möglich ist.

Wenn Sie mit erweiterter Regex-Syntax arbeiten, sind alle Wetten deaktiviert: kontextfreie Sprachen sind nicht unter Kreuzung geschlossen, so dass diese Methode nicht funktioniert.

Answer 2

Die Wkipedia article on regular expressions tut Zustand

Es ist möglich, einen Algorithmus, der für zwei gegebene reguläre Ausdrücke schreiben entscheidet, ob die beschriebenen Sprachen im Wesentlichen gleich sind, jeden Ausdruck auf einen minimalen deterministischen endlichen Automaten verringert, und bestimmt, ob sie sind isomorph (äquivalent).

gibt aber keine weiteren Hinweise.

Natürlich ist die einfache Möglichkeit, sind Sie nach ist eine Menge Tests laufen - aber wir alle wissen, die Mängel der Tests als Methode des Beweises.

Answer 3

Sie können das nicht tun, indem Sie nur auf den regulären Ausdruck schauen.

Betrachten wir den Fall, wo Sie [0-9] und [0-9]+ haben. Sie sind offensichtlich verschiedene Ausdrücke, aber wenn sie auf die Zeichenkette "1" angewendet werden, erzeugen beide das gleiche Ergebnis. Wenn sie auf die Zeichenfolge "11" angewendet werden, erzeugen sie unterschiedliche Ergebnisse.

Der Punkt ist, dass ein regulärer Ausdruck nicht genug Informationen ist. Das Ergebnis hängt sowohl von der Regex- als auch von der Zielzeichenfolge ab.