7

私は自分のコンパイラ クラスの試験前の演習をいくつか行っており、この正規表現を単純化する必要がありました。

(a U b)*(a U e)b* U (a U b)*(b U e)a*

明らかに、e は空の文字列であり、U は結合を表します。

これまでのところ、a U a = a の結合として、(a U b)* の 1 つを削除できると思います。しかし、私は他の単純化を見つけることができず、これまでのところ他の問題をうまく処理していません. :(

どんな助けでも大歓迎です、どうもありがとう！

4

4 に答える 4

3

まず、言語の英語の説明に翻訳します。

(a U b)*(a U e)b* U (a U b)*(b U e)a*

翻訳：

asまたはsの任意のシーケンスb、オプションの、、a任意の数のbsが続きます。

また

任意の数のasとbs、その後に任意のb数のasが続くオプションの

ここには多くの重複があります-少なくとも(a U b)*(a U e)、 「 sとsの(a U b)*任意のシーケンス」は必ずまたはイプシロンで終わるため（任意の文字列はイプシロンで終わる可能性があるため）、これらのグループを削除して、aba

(a U b)*b* U (a U b)*a*

翻訳：

asまたはsの任意のシーケンスとb、それに続く任意の数のbs。

また

任意の数のasとbs、任意の数のsがa続く

これで、最も外側のグループへの最初のセクションは同じなので、それらを1つにまとめましょう

(a U b)*(a* U b*)

翻訳：

任意のシーケンスのasまたはbsの後に、任意の数のasまたは任意の数のsが続きbます。

ここで、ちょっと待ってください。「AsとBの任意のシーケンス」は必ずa「 sの任意のシーケンスまたはsの任意のシーケンス」で終わりますb。つまり、最初の部分に一致するものはすべて正規表現全体に一致する可能性があります（2番目の部分はゼロの長さ）だから、私たちはそれを作ってみませんか

(a U b)*

タダ。単純。

于 2011-02-10T02:01:18.563 に答える
1

(a U b)*全体が（またはほとんどの正規表現の文法では(a|b)*）と同等だと思います

于 2011-02-10T01:56:01.623 に答える
1

正規表現では少し錆びていますが、*がまだ「ゼロ以上のオカレンス」を表している場合は、次のように置き換えることができます。

(a U e)b* for (a U b)*

これは最初の部分を次のように残します：

(a U b)*(a U b)* = (a U b)*

右側に、あなたはそれを持っています

(b U e)a* = (b U a)*

ここで、A U b = b U aなので、次のようになります。

(a U b)*(a U b)*

右側にあります

(a U b)* U (a U b)* = (a U b)*

それだけだと思います...

于 2011-02-10T01:59:58.410 に答える
0

私はそれをどのように解決するかについてのアイデアを提供します：（あまり正式ではなく、保証もありません）

メインの U の左側を見てください:

(a U b)* - どういう意味ですか? 長さ n の a´s と b´s の組み合わせ (n >= 0)。

次は (a U e) です。ここには何がありますか？a または空の単語。それが必要な場合は、前の部分ですでに取得できたはずです。e が必要な場合は、とにかく省略できます。ここで、e を選択するオプションがあるため、a を取る必要がないことに注意してください。したがって、この部分全体をスキップできます。

次は何ですか？b*. それは何ですか？私たちが望むだけのb's。前編でもゲットできたかも！私たちはそれを省くことができます!

したがって、左にあるのは (a U b)* だけです。

右側を見てみましょう：

これは簡単です。同じアイデアを使用できますが、文字が異なるだけです。

同様に (a U b)* も取得します。

したがって、最終的に (a U b)* U (a U b)* が得られます。これは、(a U b)* に等しいことがわかっています。

于 2011-02-10T02:06:31.300 に答える