4

2 つの式の補数を求める問題が演習シートに出題されています

(1)(aa|bb)*

と

(2) (a|b)(aa|bb)(a|b).

両方の補数は、私の意見では、のみまたはのみa* | b*を意味しますか?ab

4

2 に答える 2

6

通常の手順を実行する必要があります。

  • 正規表現を NFA に変換します。
  • NFA を DFA に変換します。単純なケースでは、(手動で) 正規表現から DFA に直接変換するのは簡単です。
  • すべての非最終状態を最終状態に、またはその逆にします。
  • 補完する DFA を正規表現に変換します。これは、そのような変換の 1 つの詳細な例です。

演習なので結果は示しませんが、最初の式の DFA を示します(aa|bb)*。

式1

このことから、正しい結果が得られないことがa*はっきりとわかります。Trap状態 (補足正規表現で終了状態になる) になるb*ことは決してなく、状態2a/2b (補足正規表現で非終了状態になる) になる可能性があります。

于 2013-03-16T18:09:24.247 に答える
0

単純に (aa+bb)* には、null、aa、aaaa、bb、bbbb、aabb、bbaa などのサンプル文字列が含まれます。形成できる文字列はすべて偶数の長さであり、a と b は任意の順序であることに注意してください。 、したがって、補数には奇数長の文字列 ((a+b)(a+b))*(a+b) がすべて含まれている必要があります

于 2014-08-20T19:43:32.547 に答える