오토 마토라 정규 표현

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) 인 것으로 보입니다.