6

コンパイラクラスの宿題に取り組んでいますが、次の問題があります。

奇数のaまたは奇数のb（あるいはその両方）を含むa'sおよびb'のすべての文字列の正規表現を記述します。

多くのホワイトボード作業の後、私は次の解決策を思いつきました。

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

しかし、これは私がそれを得ることができる最も単純化されたものですか？状態の数を最小限に抑えてDFAを構築し、それが単純化に役立つかどうかを確認することを検討しましたが、最初にSOの正規表現の達人に尋ねると思いました。

4

4 に答える 4

8

a（aa）*で始まり、そこから進むというGregDの推奨事項を参考にしてください。Sepp2kはほぼ正しいですが、本当の考慮事項は、他の文字を気にしないことです。つまり、「奇数のa」制約を見ているときは、文字列内のbが何であるかはまったく気にしません。したがって、b*をできるところならどこにでも貼り付けてください:)

Sepp2kの答えはほぼ正しいですが、これは正しいです：

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

詳述すると、この正規表現は、奇数のa（最初のセクション）を持つすべての文字列を計算し、それらの文字列を奇数のbを含む任意の文字列とORします。

于 2009-09-16T20:00:22.260 に答える
5

これは機能するはずです：

b* a b* (a b* a b*)* |  a* b a* (b a* b a*)*
于 2009-09-16T19:50:44.273 に答える
2

書かれている正規表現が正しいとは思わないのではないかと思います。文字列について考えてみましょう。

aba

一致するものにはいくつかの選択肢がありますが、長さが奇数であるという事実は、前面の1つだけを一致させる必要があることを意味します。

(a)(ba)

しかし、悲しいことに、そこにある2番目のメイングループを一致させることは不可能です（ba）。

このような制約を処理するとき、コア制約から始めてそこから進む方が簡単であることがわかりました。この場合、制約は「奇数」なので、

a(aa)*

奇数のを強制しaてそこから移動します。:)

于 2009-09-16T19:38:42.377 に答える
0

私はあなたが別の方法で問題に取り組む必要があると思います。

aとの両方の数が偶数でないものに一致させようとしていますb。

との偶数に一致するものから始める方がおそらく簡単でしょう。その時点であなたがしなければならないのは、あなたが実際に一致させたい最小の文字列に一致する何かを最後に追加することです。ab

于 2009-09-16T20:10:17.340 に答える