オートマトン正規表現

Question

私はこの宿題に関する質問をしています。

Which pair of regular expressions are equivalent? 
a) (ab)* and a*b* 
b) r(rr)* and (rr)*r 
c) r+ and r*r 
d) (b) and (c) 

回答は(d)と言われています。私は(b)と(c)も答えが必要だと思います。誰かが私のためにこれを明確にすることはできますか？

Answer 1

まず、各言語でいくつかの簡単な文字列を書き出すことをお勧めします。あるREの言語ではなく他のREの言語であるものを見つけたら、あなたは確かめるためにチェックすることができます。もしそうなら、あなたは完了です。以下にそのようなものを示します：

(a) 
- (ab)*: e, ab, abab, ababab, ... 
- a*b* : e, a, b, aa, ab, bb, ... 
guess: a is in L(a*b*) but not (ab)*. 
check: (ab)* only generates strings with the same number of a's as b's. 
L((ab)*) != L(a*b*) 

(b) 
- r(rr)*: r, rrr, rrrrr, rrrrrrr, ... 
- (rr)*r: r, rrr, rrrrr, rrrrrrr, ... 
guess: these look the same. 
proof: the first generates all and only strings of r's of odd length. 
     the second generates all and only strings of r's of odd length. 
     these languages are the same. 
     alternatives: 
     - derive DFAs L and R and show DFAs for L \ R and R \ L accept 
      the empty language. 

(c) 
- r+ : r, rr, rrr, rrrr, ... 
- r*r: r, rr, rrr, rrrr, ... 
guess: these look the same. 
proof: the first generates all and only non-empty strings of r's. 
     the second generates all and only non-empty strings of r's. 
     these languages are the same. 
     alternatives: 
     - derive DFAs L and R and show DFAs for L \ R and R \ L accept 
      the empty language 

上記に基づいて、最も正しい答えは（d）であるように見えます。