regulärer Ausdruck "enthält" einen anderen regulären Ausdruck

Question

Gibt es eine Möglichkeit zu testen, ob ein regulärer Ausdruck einen anderen regulären Ausdruck "enthält"?
Zum Beispiel:

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b"; 

RegEX1 "enthält" RegEX2.

Soweit ich weiß - das kann nicht gemacht werden, liege ich falsch?

---

OK, Joel.Neely hat gezeigt, dass es getan werden kann (habe es noch nicht gelesen ...) akademisch.

Kann es in einer Programmiersprache gemacht werden, sagen wir C#?
Wie effektiv wird das sein? Wie lange dauert es, 1000 Paare zu testen?

Answer 1

Ja.

This paper enthält eine detaillierte Diskussion des Themas (siehe Abschnitt 4.4).

Answer 2

Die Umwandlung der beiden Ausdrücke in die entsprechenden Zustandsautomaten und die Überprüfung aller Pfade in beiden Maschinen ermöglichen die gleichen Übereinstimmungen, sollten den Trick tun. Die Pump-Lemme sollte offensichtlich darauf ausgerichtet sein, also vermeiden Sie alte Knoten erneut zu besuchen.

Es würde nur für "einfache" reguläre Ausdrücke funktionieren (oder real, was hast du, perls rekursive Ausdrücke sind viel ausdrucksvoller).

Während ein Graph der Zustandsmaschine eine große Anzahl von Pfaden haben kann, sollte er immer noch begrenzt sein (besonders wenn die Quelle für die Ausdrücke menschlich ist). Sie würden also alle zulässigen Pfade von RegEX1 finden und nacheinander prüfen, ob es in RegEX2 zulässig ist. Wenn alle Pfade gültig sind, wissen Sie, dass der eine in dem anderen enthalten ist.