10

For example, in an assignment given to me, we were asked to find out if two regular expressions are equal or not.

(a+b+c)*  and ((ab)**c*)*

My question is how is one supposed to do that? If I draw the transition graphs for both and then run a few strings through it and show that both of the TGs are able to accept it, is that a sufficient proof ? If not, how do I do it? Is there a mathematical/axiomatic approach towards this?

Thanks in advance.

EDIT: There is another thing that I'd like to clear which is kind of related to this question. Are the two FAs depicted in the photo below the same?

enter image description here

i.e. Are (1) and (2) in the above picture the same?

4

6 に答える 6

7

それらが等しいかどうかを判断するアルゴリズムがあります。

  1. Kleeneの定理を使用して、各REに対応するNFAラムダを構築します
  2. サブセット/パワーセット構造を使用して、それぞれのDFAを構築します
  3. （オプション）標準のDFA最小化アルゴリズムを使用してDFAを最小化します。
  4. デカルト積機械の構築を使用して、L（M1）\ L（M2）およびL（M2）\ L（M1）のDFAを構築します
  5. （オプション）これらのCPMを最小化します。
  6. サイズが|Q|以下のアルファベットEのすべての文字列をテストして、それぞれが文字列を受け入れるかどうかを判断します。（正規言語のポンピング補題により機能します）

目新しさや天才は必要ありません。これを行うプログラムを作成することもできます（ただし、実際には、パワーセット構造を使用すると扱いにくくなり、両方のステップで最小化に失敗するとコストがかかる可能性があります）。

編集：はい、それらのDFAは同じです。1つ目は、2つ目の省略表記です。

于 2012-01-22T15:51:07.500 に答える
4

R によって定義された言語 (つまり、正規表現 R によって生成された文字列のセット) が T によって定義された言語と等しい場合、2 つの正規表現 R と T は等価です。正規表現の等価性を証明するために、集合論からの包含証明を使用します。 . つまり、S1 が正規表現 R によって生成された文字列の集合であり、S2 が正規表現 T によって生成された文字列の集合である場合、S1 ⊆ S2 および S2 ⊆ S1 であることを証明する必要があります。集合が等しいことを証明するには、両方向が必要です。

-- CSc 4340 GSU Fall 09 (Dr. Raj Sunderraman) の講義ノートより

于 2012-01-22T14:39:35.577 に答える
3

仮定

  1. 説明のためにスペースが挿入されています
  2. ( ( a b )* * c* )*実際には((ab)*c*)**、
  3. 各パターンは と で囲まれ^て$います。

これらの正規表現は同じではありません。

abccabcc一致しない(a+b+c)*が一致する((ab)*c*)*

どうやってこれを見つけたのですか？

それらのパターンをよく見てみると、2つのことがわかりました。

  1. 最初のものは a と b の複数を受け入れます{1,}。したがって、常に a のシーケンスと b のシーケンスが並んでいます。aaaabb、aabbbbb など。ただし、2 番目のパターンでは、a と be が 1 つのインスタンスと並んで表示されます。ab、アババブ、アバババブなど。
  2. c は、a のシーケンスと b のシーケンスに続いて 1 回だけ表示されます。しかし、2 番目のパターンでは、c は何度でも使用できます。
于 2012-01-22T14:22:45.837 に答える
0

それらは異なっており、量指定子によって簡単にわかります。最初の式が何かに一致するには、. が含まれている必要がありますc。2番目は明らかになしで行うことができますc。（他にも多くの違いがありますが、それで始められるはずです）。

于 2012-01-22T14:36:09.640 に答える
-1

((ab)^^c^)^=( a^b^c^)^ = (a+b+c)^

于 2016-08-22T04:57:50.403 に答える
-5

これは宿題なので、完全な答えは示しませんが、知っておく必要がある重要な事実をお伝えします。特定の有限状態言語について、最小数の状態でそれを認識する DFA は一意です。

ところで、あなたの教授がやり方を教えずにこの宿題を出すとは思えません。インターネットから離れて、講義ノートや教科書を読んでください。

于 2012-01-22T16:01:57.487 に答える