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

Question

Ich arbeite für mein Compiler Klasse auf einige Hausaufgaben und ich habe folgendes Problem:

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.

Answer 1

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.

Answer 2

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. :)

Answer 3

Diese Arbeit sollte:

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

Answer 4

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.