|
|
Meine Frage:
Da ich aus der praktischen Ecke komme, hier eine auf konkrete Softwareentwicklung bezogene Frage:
Gegeben seien zwei reguläre Ausdrücke X und Y, z.B.
X = "^ABC.*" und
Y = "^AB.*C", mit denen ich Strings untersuchen will.
Gibt es Algorithmen, mit denen ich Aussagen erhalte, ob die Schnittmenge von X und Y (alle Ausdrücke, die mit X und Y matchen) leer ist? Wie kann ich das prüfen? Gibt es auch Algorithmen, die mir sagen, ob die Menge aller Strings, die mit X matchen, aber nicht mit Y, leer ist?
Beispiel:
P = "^ABC.*"
Q = "^AB.*"
Die Menge aller Ausdrücke, die mit P matchen minus die Menge aller Ausdrücke, die mit Q matchen, ist leer. Kann man das systematisch untersuchen? Es reichen Methoden für ganz einfache Ausdrücke. Wie kann ich hier vorgehen, ohne mit Automaten alle möglichen Strings prüfen zu müssen? Wo finde ich überhaupt Information zu dem Thema?
Meine Ideen:
Für UND:
Vermutlich würde ich Zeichenweise die Ausdrücke durchlaufen und ähnlich wie bei einem Test auf Gleichheit schauen, ob
- Entweder die Zeichen identisch sind
- Oder aber in X ein Generator ist, der auf Y passt,
- oder umgekehrt
- oder in beiden ein Generator ist, und ob gleiche Zeichen erlaubt sind
Nehmen wir mal an, wir hätten nur Ausdrücke mit .*, .+ und .? zur Verfügung (entspricht den üblichen Wildcards). Dann müsste das Problem doch so gut zu lösen sein, oder?
|
|
