私は私のコンパイラのクラスのためにいくつかの宿題に取り組んでいると私は次のような問題があります。この正規表現をさらに単純化することはできますか？
はの奇数を含ん年代とB年代のすべての文字列のための正規表現を書きますまたは奇数のb（またはその両方）です。私は、次の解決策を考え出したホワイトボードに多くの作業の後
：
(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*
しかし、これは私がそれを得ることができる最も単純化されますか？私はDFAの構築を検討して、州の数を最小限に抑えて、それが簡素化するのに役立つかどうかを見極めましたが、私は最初に正規表現の達人に尋ねました。
は、*（AA）で始まり、そこから行くのグレッグD'sの勧告を取ります。 Sepp2kはほぼ正しいですが、実際の考慮事項は、あなたが他の手紙を気にしないことです。私が意味することは、「奇数のa」制約を見ているときに、あなたの文字列内にbが何であるかは全く気にしないということです。したがって、あなたは
Sepp2kの答え:)をすることができスティックB * 'sの任意の場所にはほとんど右ですが、この1つは正しいです：
b* a b* (a b* a b*)* | a* b a* (b a* b a*)*
詳述すると、この正規表現はの数が奇数ですべての文字列を割り出し（最初のセクション）、ORは奇数のbを含む文字列を持つ文字列です。
@ Walt W、私はペースでこれを実行していますが、あなたは正しいと思います。 – mmcdole
偶数のaと偶数のbを含む文字列の正規表現を教えてください。 –
aの数が偶数かbの数が偶数であることを意味しますか？私は、あなたがゼロ長の先読みでANDをやることができると思います...それは標準的な正規表現ではありません。この方程式を奇数から偶数に変更する場合は、各セグメントの最初の2つの項を削除します（左側からb * a、右側からa * b） –
私はあなたの正規表現が書かれているとは信じられないと思います。文字列を考えてみましょう：
aba
我々は試合のためのカップルの選択肢を持っているが、それは奇数長だという事実は、私たちが、フロントで唯一のAと一致しなければならないことを意味する：
(a)(ba)
しかし、悲しいことに2番目のメイングループが（ba）と一致することは不可能です。
このような制約を扱う場合、コアの制約から始めてそこから行く方が簡単です。この場合、あなたの制約は「奇数、」そうa年代の奇数を強制的に
a(aa)*
で始まり、そこから行くです。 :)これは動作するはず
@Greg D、それは本当です。私はそれについて少し考えてみましょう。 – mmcdole
：
b* a b* (a b* a b*)* | a* b a* (b a* b a*)*
私は似たようなものを書いていました:)この正規表現は奇数のa（最初のセクション）を持つすべての文字列を取り出し、ORは奇数のbを含む文字列を持つ文字列です。最初の項は最後にb *を必要とし、2番目のオプションは最後に*が必要なので、ここでは若干のエラーがあります。そうしないと、abbbaは受け入れられません。 –
@ sepp2k、これはすべてのテストケースで機能しています。あなたがそれを作っていたときに思考プロセスを記述できますか？それは私が降りていた道よりはるかに簡単です。 – mmcdole
あいまいではないと誰も言わなかった。ウォルトは正しいです、それは終わっていませんが、すべての重要なビットがそこにあります。 :) –
私はあなたが問題に異なってアプローチする必要があると思います。
aとbの両方の偶数番号を持たないものと一致させようとしています。
数字がaとbであっても、それはおそらくより簡単でしょう。その時点でやらなければならないことは、実際に一致させたいと思う最小の文字列に一致するものを最後に追加することだけです。
regexの高度な機能をどのように使用できますか？ –
彼はPCREやposix正規表現ではなく、コンピュータサイエンスで正規表現を使用しています;）それらは異なっています。 –
@ブラッドギルバート、私は、これまであまり多くはない本で紹介されている正規表現を使用することが許されていると仮定します。 （*、+、？、|、[]、^）。かなり平野。 –