Determining if two languages are equal [Regular expression] [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

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 :)

Answer 1

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.

Answer 2

Assume for the sake of contradiction that R1 ⊆ R2. Therefore every string, s, in R1 is also in R2.
Let s = "1001", which is a member of R1; however, s is not a member of R2. =><=

Since R1 is not a subset of R2, so all you need to show is a counterexample.