Automaten regulären Ausdruck

Question

Ich habe diese Hausaufgabe Frage.

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) 

Ich habe gesagt, dass die Antwort (d) ist. Ich denke, und (c) sollten auch Antworten sein. Kann jemand das für mich klären?

Answer 1

Das erste, was Sie versuchen sollten, ist ein paar einfache Strings in jeder Sprache zu schreiben. Wenn Sie eine finden, die in der Sprache eines RE ist, aber nicht die andere, können Sie überprüfen, ob und wenn Sie fertig sind. Hier ist, was das wie für diese aussieht:

(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 

auf der oben Basierend, die richtige Antwort scheint zu sein, (d).