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

Question

Ich arbeite an einigen Hausaufgaben für meine Compiler Klasse und ich habe folgendes Problem:

Schreiben Sie einen regulären Ausdruck für alle Strings von a s und b 's, die eine ungerade Anzahl von a enthalten ist oder ein ungerade Anzahl von b 's (oder beides).

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

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

Dies ist jedoch ist die vereinfachte ich es bekommen kann? Ich habe als die DFA konstruieren versucht, die Anzahl der Zustände dort zu minimieren, um zu sehen, ob es mir helfen würde, zu vereinfachen, aber ich dachte, ich würde auf SO zuerst die regex Gurus fragen.

Answer 1

Nehmen Sie Greg D's Empfehlung mit einem (aa) des Beginnens * und gehen von dort aus. Sepp2k hat es fast richtig, aber die wirkliche Überlegung ist, dass Sie nicht über den anderen Brief kümmern. Was ich meine ist, wenn Sie an der „ungeraden Anzahl von einer der“ Zwang suchen, kümmert es dich nicht darum, was bs sind in der Zeichenfolge. So Stick b * 's überall möglich:)

Sepp2k Antwort ist fast richtig, aber dies ist richtig:

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

Um dies näher auszuführen, nach dieser Frist regex Sie alle Saiten mit einer ungeraden Anzahl von Einsen (erster Abschnitt) und OR ist diese Zeichenfolgen mit beliebigen Zeichenketten eine ungerade Anzahl von bs enthält.

Answer 2

Dies sollte funktionieren:

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

Answer 3

Ich habe Angst, dass ich glaube, dass Ihr Regex nicht so 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, dass wir einen einsamen ein an der Vorderseite übereinstimmen müssen, so:

(a)(ba)

Aber leider ist es unmöglich für Ihre zweite Hauptgruppierung dort übereinstimmen (ba).

Wenn Sie mit einer Einschränkung, wie dies zu tun, fand ich es einfacher, aus dem Kern Zwang zu starten und geht von dort aus. In diesem Fall Ihre Einschränkung ist „ungerade“, so beginnen Sie mit

a(aa)*

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

Answer 4

Ich glaube, Sie müssen anders das Problem nähern.

Sie versuchen, etwas zu entsprechen, die nicht einmal Zahlen sowohl a und b haben.

Es wäre wahrscheinlich einfacher sein, mit etwas zu beginnen, die übereinstimmt noch Zahlen von a und b. Alles, was Sie an diesem Punkt zu tun haben, wäre etwas am Ende hinzuzufügen, die die kleinste Zeichenfolge übereinstimmt, die Sie tatsächlich übereinstimmen sollen.