 Schnittmengen zu regulären Ausdrücken bestimmen |
d025477
Grünschnabel
Dabei seit: 22.01.2011
Beiträge: 1
 |
|
| Schnittmengen zu regulären Ausdrücken bestimmen |
     |
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?
|
|
22.01.2011 00:42 |
|
|
aal
unregistriert
|
|
Deine Ideen sind schon richtig. Dennoch ist mir dein Problem nicht ganz klar.
Laut der Definition einer Schnittmenge ist das Ergebnis aus X schnitt Y =" ^ABC.*" . Denn das enthält die Menge aller chars(Teile) des Strings, die in bei den beiden Strings X und Y vorhanden sind.
Warum soll nur eine leere Menge entstehen ?
Wenn du die chars ,also die einzelteile des Strings vergleichst=> keine leere Menge
Wenn du die Strings miteinander Vergleichst mit z.B. x.equals(y) = ist es false.
Nimm doch einfach eine Programmiersprache zur Hilfe. Mit ihr kannst du die Algorithmen nachbilden und auch testen, ob sie wircklich funktionieren.
Ein Beispiel in Java , für die bestimmung der Schnittmenge:
String x ="^ABC.*"
String y="^AB.*C"
char x [] = x.toCharArray;
char y [] = y.toCharArray;
char schnittm []= new char[6];
// Schnittmenge der beiden Strings
for ( int i= 0 ; i<x[].legnth; i++)
{
for ( int y=0;y<y[].lenght;y++)
{
if( x[i]==y[y] )
{
schnittm= y[y]; // array mit dem Ergebnis
}
}
}
|
|
|
23.01.2011 10:18 |
|
|
|
