Minimal? Gleichheit?

[Psychopath]

Guten Abend,

zunächst der Hinweis, dass ich die Suchfunktion bemüht, aber nichts gefunden habe.
Zu meiner Problemstellung habe ich auch sonst im Internet nichts finden können, was, wie ich befürchte, eventuell daran liegt, dass es das von mir Geforderte (noch) nicht gibt. Ich hoffe, dass ihr mich da eines besseren belehren könnt!

Also es geht darum, dass ich einen regulären Ausdruck vorliegen habe, und dieser mir sehr komplex erscheint. Deshalb würde ich ihn gerne minimieren, weiß aber nicht, ob das überhaupt möglich ist oder ob er schon minimal ist.

Eine zweite Problemstellung wäre zwei vorliegende reguläre Ausdrücke auf Gleichheit zu überprüfen. Dazu konnte ich ebenfalls nichts finden.

Ich bedanke mich für Hilfe,
Grüße

[smg]

Na ja um nen Regex zu verkürzen zu Optimieren musst du einfach überlegen, für das Zweitere kannst du vielleicht visual-regexp benutzen dann siehst du ob sie das gleiche matchen.

[Psychopath]

Na ja um nen Regex zu verkürzen zu Optimieren musst du einfach überlegen, für das Zweitere kannst du vielleicht visual-regexp benutzen dann siehst du ob sie das gleiche matchen.

Okay, ich habe mir hieran die Zähne ausgebissen, vielleicht fällt Dir ja etwas ein. Ich soll zu der durch diesen (http://www.cwiwie.de/ndea.jpg) NDEA erzeugten Sprache einen regulären Ausdruck angeben.

Meine Lösung bisher:
((1+e)0*(0+1)*10)+

e steht hier für das leere Wort (Epsilon) und das Plus hinter der Klammer für aa*, also mindestens eine Wiederholung...

Edit: Eben hatte ich den falschen Graphen hochgeladen, ist jetzt korrigiert.

[smg]

Wo sind Stopzustände? Alle?

[Psychopath]

Wo sind Stopzustände? Alle?

Nope, nur der rechte untere doppeltumrandete Knoten.

[smg]

Mh, ich würd jetzt spontan das sagen:

[01]+((1|0)(1|0))+0

was ja auch nicht viel kürzer ist :))

[Psychopath]

Mh, ich würd jetzt spontan das sagen:

[01]+((1|0)(1|0))+0was ja auch nicht viel kürzer ist :))

Mein WG-Kollege hatte die Lösung noch, es ist folgender:

((0+1)*10)

Ich hab irgendwie noch enorme Schwierigkeiten damit, anhand eines EA einen entsprechenden regexpr zu finden... In diesem Falle hab ich gerade erkannt, dass es besser gewesen wäre vom Ziel zum Anfang hinzuarbeiten und nicht umgekehrt... Ich hätte noch Stunden weitergesucht, wenn er mir nicht die Lösung verraten hätte...

Naja, vielen Dank Dir, für die späte Hilfe! Nach dem Tool, das du mir empfohlen hast werde ich mal schauen.

Gute Nacht!
Gruß

[smg]

Mh cool, aber erkennt das Ding sicher nicht auch Sachen die es nicht soll?
((0+1)*10)

[Psychopath]

Also ich hab bis jetzt keine Wörter entdeckt...
Gibt's denn welche?

Gruß

[smg]

Ne scheinbar nicht, habs mal auspropeirt passt :)

[Jan Krüger]

Erster Schritt wäre für mich, den Automaten zu minimieren. Da kann man direkt als erstes mal den Zustand q3 eliminieren, denn von q2 aus kann man für die gleich Übergänge stattdessen auch nach q1 gehen. Als nächstes kann man sehen, dass jedes Wort immer auf 0 enden muss (es gibt keinen anderen Übergang zum Endzustand) und dass davor eine 1 kommen muss (es gibt keinen anderen Übergang davor); folglich kann kein weiterer Knoten entfernt werden (zwei Übergänge = drei Zustände).

Wir sind jetzt also soweit, dass wir wissen, dass jedes Wort auf 10 enden muss. Sehen wir uns nun den allgemeinsten Fall eines Worts davor an, dann ist das eine beliebige Zeichenfolge (q0 -> q0) gefolgt von 10. Damit wären wir beim Endergebnis: (0+1)*10.

[Psychopath]

Jep, so habe ich's mir dann auch klargemacht, nur fiel es mir extrem schwer, darauf zu kommen.
Anscheinend kann man zur Analyse oder Inhaltserfassung eines solchen Automaten wie folgt vorgehen
1) Minimierung des Automaten
2) Regelmäßigkeiten aller Kanten in Endzustände erfassen (Wortende)
3) Regelmäßigkeiten aller Kanten aus Startzustand erfassen (Wortanfang)
4) Übergänge zwischendrin auf Regelmäßgkeiten analysieren

Zu dem Thema der Minimierung eines regulären Ausdrucks habe ich übrigens noch einen interessanten Link (http://publikationen.ub.uni-frankfurt.de/volltexte/2007/4577/) gefunden, den ich wegen der P/NP Problematik noch nicht ganz erfassen kann. Dazu brauche ich mal einen ruhigen Tag ohne Lernstress...
Die überwiegende Verwendung des Konjunktivs in diesem Artikel hat mich dazu veranlasst, eine Möglichkeiten der Minimierung erst einmal nicht komplett auszuschließen (immer positiv denken ;-) ).

[Jan Krüger]

Auf jeden Fall sagt uns dieser Artikel, dass die Minimierung eines regulären Ausdrucks wirklich ausgesprochen schwierig ist. Das ist doch beruhigend. :)