preparing for an exam and was going through this problem:
Determine whether the set of strings represented by R1 is a subset of R2?
R1 = (01 +10)* R2 = ((01)* + (10)*)
My attempt: Since there represent the same expression I tried to prove that they are the same R1 ⊆ R2
I tried to show R2 is the same as R1: so i tried this, using the regular expression equivalence theorem:
((01 + ε)* + (10 + ε)) = (01 + ε) + (10 + ε)*
now i am stuck, i am thinking of applying the associativity rule here and showing that (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10)* // I think this step might be wrong
thus R2 = R1
The step: (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10)*
I think is wrong, i think i am applying the associativity law wrong, I don't know how to use it when it has * on it. Any help on it would be appreciated. Please :)
I haven't done proofs in a little while, but I would think that a simple counterexample proof would be enough here.
Start with the assertion that R1 is a subset of R2 (strict or not shouldn't matter).
Note that R1 can produce the following string (assuming + means OR, so R1 can produce either 01 or 10 in any pattern infinitely):
10 01
You can observe that it is impossible to produce this string in R2, since R2 is defined such that it must have either only 01 pairs, or only 10 pairs.
Therefore, since R1 can produce strings outside of the domain of R2, it is impossible for R1 to be a subset, strict or not, of R2.