regex - DFA を使用せずにオートマトン理論で 2 つの正規表現が同等であることを示す

Question

2 つの正規表現が同等であることを証明しようとしています。同じ言語を定義している場合、2 つの正規表現が同等であることはわかっています。しかし、DFA を使用せずにそれを証明する方法はありません。

たとえば、次のものが同等であることを証明する問題があります。

(a + b)*a(a + b)*b(a + b)* = (a + b)*ab(a + b)*

これらは両方とも、少なくとも 1 つの 'a' と 1 つの 'b' を持つ言語を定義していることを知っています。

以下も同様です。

(a + b)*ab(a +b)* + b*a* = (a + b)*

どんな助けでも大歓迎です。

ありがとう

Answer 1

この正規表現レクチャーのスライド 16 の ID を使用してそれらを証明できるはずです 。特に、9 番目の恒等式の最後の等号、R* = RR*+e を巧みに使用することをお勧めします。

ところで、第一言語は正確には「少なくとも 1 つの 'a' と 1 つの 'b'」ではありません。たとえば、'ba' は言語に含まれていませんが、少なくとも 1 つの 'a' と 1 つの 'b' を含んでいます。