Ist es möglich, diesen regulären Ausdruck weiter zu vereinfachen?

Ich arbeite für mein Compiler Klasse auf einige Hausaufgaben und ich habe folgendes Problem:Ist es möglich, diesen regulären Ausdruck weiter zu vereinfachen?

einen regulären Ausdruck, die eine ungerade Anzahl von enthalten für alle Saiten einer ‚s und b‘ s schreiben a 's oder eine ungerade Anzahl von b' s (oder beide).

Nach vielen Whiteboard Arbeit, die ich mit der folgenden Lösung kam:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

Allerdings ist dies die vereinfacht ist, ich es bekommen kann? Ich habe überlegt, das DFA zu konstruieren, indem ich versuche, die Anzahl der Zustände zu minimieren, um zu sehen, ob es mir helfen würde zu vereinfachen, aber ich dachte, ich würde die Regex-Gurus zuerst nach SO fragen.

Quelle

2009-09-16 Anonymous

Welche erweiterten Funktionen von Regex dürfen Sie verwenden? –

er verwendet reguläre Ausdrücke in der Informatik, nicht PCRE oder Posix Regex;) Sie sind anders. –

@Brad Gilbert, ich nehme an, wir dürfen nur die Regex verwenden, die bisher in dem Buch eingeführt wurde, das nicht viel ist. (*, +,?, |, [], ^). Ziemlich einfach. –

Greg Nehmen D's Empfehlung mit einem (aa) des Beginnens * und gehen von dort aus. Sepp2k hat fast recht, aber die wirkliche Überlegung ist, dass Sie sich nicht um den anderen Brief kümmern. Was ich meine ist, wenn Sie sich die Bedingung "ungerade Anzahl von Einsen" anschauen, ist es Ihnen egal, welche Bs in Ihrer Zeichenfolge sind. So Stick b * 's überall können Sie

Sepp2k Antwort ist fast richtig, aber dieses ist richtig:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

zu erarbeiten, diese Regex mit einer ungeraden Anzahl von Einsen alle Strings Figuren aus (erster Abschnitt), und OR sind diese Strings mit beliebigen Strings, die eine ungerade Anzahl von b enthalten.

Quelle

2009-09-16 20:00:22

@Walt W, Ich laufe diesen hier auf Herz und Nieren, aber ich denke du hast Recht. – mmcdole

Bitte sagen Sie mir den regulären Ausdruck für jede Zeichenfolge, die gerade Anzahl von a und gerade Anzahl von b enthalten? –

Meinst du eine gerade Zahl von a ODER eine gerade Anzahl von b? Ich nehme an, du könntest ein AND mit look-heads von null Länge machen ... Das ist aber kein normales Regex-Zeug. Wenn Sie diese Gleichung von ungerade auf gerade ändern möchten, löschen Sie einfach die ersten zwei Terme jedes Segments (b * a von der linken Seite und a * b von der rechten Seite) –

Ich habe Angst, dass ich nicht glaube, dass Ihre Regex wie geschrieben korrekt ist. Betrachten Sie die Zeichenfolge:

aba

Wir haben ein paar Entscheidungen für die Spiele, aber die Tatsache, dass es mit ungerader Länge bedeutet, ist wir ein einsames eine an der Vorderseite übereinstimmen müssen, so:

(a)(ba)

Doch leider Es ist unmöglich, dass Ihre zweite Hauptgruppe dort übereinstimmt (ba).

Wenn ich mich mit einer solchen Einschränkung beschäftige, ist es einfacher, von der Kernbeschränkung auszugehen und von dort aus zu gehen. In diesem Fall ist der Zwang „ungerade“, so beginnen mit

a(aa)*

eine ungerade Anzahl von a ‚s zu zwingen, und gehen von dort aus. :)

Quelle

2009-09-16 19:38:42

@Greg D, das ist wahr. Lass mich für eine Sekunde darüber nachdenken. – mmcdole

Diese Arbeit sollte:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

Quelle

2009-09-16 19:50:44 sepp2k

Ich habe etwas Ähnliches geschrieben :) Um dies auszuarbeiten, berechnet diese Regex alle Strings mit einer ungeraden Anzahl von a's (erster Abschnitt), und OR ist jene Strings mit beliebigen Strings, die eine ungerade Anzahl von b enthalten. Es gibt jedoch einen kleinen Fehler, da der erste Term b * am Ende benötigt und die zweite Option am Ende ein *. Andernfalls wird abbba nicht akzeptiert. –

@ sepp2k, das funktioniert in allen meinen Testfällen. Kannst du deinen Denkprozess beschreiben, als du das gemacht hast? Es ist viel einfacher als der Weg, den ich ging. – mmcdole

Niemand sagte, dass es nicht zweideutig sein kann. Walt ist richtig, es ist noch nicht fertig, aber alle wichtigen Teile sind da. :) –

Ich denke, dass Sie das Problem anders angehen müssen.

Sie versuchen, alles anzupassen, das keine geraden Zahlen von a und b hat.

Es wäre wahrscheinlich einfacher, mit etwas zu beginnen, das sogar Zahlen von a und b entspricht. Alles, was Sie zu diesem Zeitpunkt tun müssen, wäre etwas an dem Ende hinzuzufügen, das der kleinsten Zeichenfolge entspricht, die Sie tatsächlich abgleichen möchten.

Quelle

2009-09-16 20:10:17

Ist es möglich, diesen regulären Ausdruck weiter zu vereinfachen?

Antwort

Verwandte Themen