Regulärer Ausdruck Problem

Was ist der reguläre Ausdruck für die Sprache 0 ^{m n} wo m + n ist gerade?Regulärer Ausdruck Problem

Quelle

2010-03-09 erasmus

Entweder ich bin müde oder Ihre Frage macht sehr wenig Sinn. –

Ich glaube nicht, dass dies etwas mit Regexp zu tun hat ... –

@Andy E: Es ist nicht, weil du müde bist, Kumpel. –

Wenn Sie einen String 000...111... bedeuten, wobei die Länge der Saite selbst ist, können Sie ^(00)*(01)?(11)*$

Quelle

2010-03-09 15:31:07 SLaks

Dies ist keine Antwort, weil es auch 00 01 1 11 validiert, deren Länge nicht gerade ist. – erasmus

Das ist, weil ich vergessen habe, die Regex zu verankern. Es funktioniert jetzt korrekt. – SLaks

+1 für die Antwort. Wie stimme ich Ihnen jetzt zu, um die Frage überhaupt zu verstehen? – Amarghosh

Ok verwenden, so müssen Sie für Null die Fälle berücksichtigen, wenn es seltsam und wenn sie gerade sind. Dies erfordert zwei Zustände, einen für gerade Nullen, einen für ungerade Nullen. Dann für die ungerade Null-Fall müssen Sie 1 eins dann eine gerade Anzahl von Einsen haben. Für den geraden Fall brauchen Sie nur eine gerade Anzahl von Einsen.

Es ist einfach die DFA zu schreiben, aber ich weiß nicht, wie es hier plotten, also werde ich eine Vermutung auf den regulären Ausdruck zu wagen:

(0 (00)* 1 (11)*) \/ (00)*(11)*

Quelle

2010-03-09 16:02:08

Hier sind geplottete Maschinen für diesen Regex. Vollständige NFA: http://static.max99x.com/misc/nfa.png. Gesäuberte NFA: http://static.max99x.com/misc/nfa2.png. Minimierte DFA: http://static.max99x.com/misc/dfa.png. –

@Max: Super! Ist das ein Werkzeug deines eigenen Designs? Ich erinnere mich an die Implementierung eines NFA auf minimalen DFA-Konverter vor vielen Jahren, aber es kam mir nie vor, es mit graphviz zu rendern :) –

@ Il-Bhima: Yeah. http://max99x.com/school/automate-editor. Könnte etwas buggy sein, da es ein schnelles Schulprojekt war. –

Antwort

Verwandte Themen