1

次の正規表現の同等性は真ですか? なぜですか、そうでないのですか？

(ab)* u (aba)* = (ab u aba)*

*=クリーネスター

u=Union (集合論)

4

2 に答える 2

5

いいえ、それらは同等ではありません。RHS の言語には「abaab」が含まれていますが、LHS の言語には含まれていません。これらの間に何か関係はありますか？はい; しかし、私はあなたに答えを与えるだけではありません。ヒント: LHS にない RHS の文字列はありますか?

編集：

興味のある読者のために少しだけ説明します。言語は文字列のセットです。したがって、集合間の関係は言語間の関係でもあります。最も一般的なセットの関係は、等価、サブセット、およびスーパーセットです。宇宙集合 U1 と U2 上の 2 つの集合 A と B が与えられた場合、集合 A は、宇宙集合 U1 u U2 (u は和集合を表す) の下の B の部分集合であり、ただし、A のすべての要素が B の要素でもあります。同様に、2 つの集合 A が与えられた場合、および B がユニバース セット U1 および U2 を超える場合、セット A はユニバース セット U1 u U2 の下の B のスーパーセットです (u は和集合を表します)、B のすべての要素が A の要素でもある場合 (同等に、B が A のサブセットである場合) . セット A と B は、A が B のサブセットであり、B が A のサブセットである場合に等しい (同等に、A が B のスーパーセットであり、B が A のスーパーセットである場合)。2 つのセット A と B は、これら 3 つの関係のいずれにも属さないことに注意してください。

セット A と B の間に存在する可能性のある 4 つの関係 (等値、サブセット、スーパーセット、なし) のどれを見つけるには、通常、A が B のサブセットであるかどうか、および B が A のサブセットであるかどうかを確認します。最初のチェック B1 と 2 番目のチェックを呼び出します。ここで、B1 と B2 はブール変数であり、チェックに合格した場合に真になります (つまり、B1 の場合、A は B のサブセットであり、B2 の場合、B は A のサブセットです)。次に、(B1 && B2) は等価に対応し、(B1 && !B2) はサブセットに対応し、(!B1 && B2) はスーパーセットに対応し、(!B1 && !B2) は関係なしに対応します。

上記の例では、RHS に LHS にはない要素が含まれていることを示すことで、2 つの言語が等しくないことを示しています。これにより、「A は B のスーパーセットである」という関係も除外されることに注意してください。2 つ残っています。B は A のスーパーセットであるか、それらの間に関係はありません。これを判断するには、A が B のサブセットであるかどうかを判断する必要があります。LHS 言語の要素がすべて RHS 言語であるかどうか。その場合、LHS はサブセットです。そうでなければ、関係はありません。

1 つのセットに要素があり、別のセットには要素がないことを示すための最も簡単で説得力のあるアプローチは、反例による証明です。これが私が採用したアプローチです。明示的に名前を付けなくても、言語にそのような要素が含まれている必要があるという議論を行うこともできます。この種の証明は、正しく行うのが非常に難しい場合があります。

集合 A のすべての要素が集合 B にもあることを示すには、より一般的な証明手法が必要になります。帰納法による証明と矛盾による証明は、一般的な例です。帰納的証明を行うには、言語の各文字列に明示的または暗黙的に自然数を割り当て、単純な引数を使用して主張 (この場合、要素が他のセットの要素でもある) が真であることを示します。 . 次に、セット内の最初の n 個の要素 (与えられた番号に従って) が true であると仮定し、その後に続くすべての要素も要求を満たさなければならないことを示します。矛盾による証明を行うには、証明したいことの反対を仮定し、矛盾を導き出します。あなたが成功し、あなたの主張が間違っているという唯一の仮定があった場合、あなたの主張は最初から真実だったに違いありません.

于 2011-10-17T18:54:50.710 に答える
1

いいえ、同等ではありません。

類似点：

  1. どちらも空の文字列を受け入れます
  2. どちらも「ababa」 （regex2の最小表現）を受け入れます

違い：

  1. abとabaは、 regex1に一度だけ表示される場合と表示されない場合があります。これは、regex2とは異なり、表示される場合と表示されない場合がありますが、組み合わせて表示されます。

違いが出たので、同等ではないと言えます。

しかし

正規表現は正規表現の表現（説明ではない）であるため、式を見ただけではregex1がregex2と同等であるとは言えません。それを証明するために（数学的な証明）、これらの正規表現をNFAに変換できます（非決定性有限オートマトン）またはDFA（決定性有限オートマトン）を使用して、差異を比較します。

于 2011-10-17T19:21:32.560 に答える