4

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

Rave
  • 835
  • 4
  • 15
  • 28
  • 1
    I haven't done these proofs in quite some time, but at first glance, it appears that r2 is a subset of r1 but that r1 is not a subset of r2. – doog abides Dec 06 '13 at 05:50
  • 4
    This question appears to be off-topic because it is not a programming question. Try http://cs.stackexchange.com/ – Raymond Chen Dec 06 '13 at 06:33

2 Answers2

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.

Steve P.
  • 14,489
  • 8
  • 42
  • 72
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.

ajp15243
  • 7,704
  • 1
  • 32
  • 38
  • I know, I was irritated at myself for not typing faster! Edit: And also for misinterpreting R2's definition, fixed that. – ajp15243 Dec 06 '13 at 06:16
  • I don;t quite get why we can only get 01 or 10 pair from R2, Can't we choose both? Also from R1 can we get the 1001 pair? or is it only 10 or 01 – Rave Dec 06 '13 at 13:16
  • @Rave The `10 01` just has the space for convenience, consider it the same as `1001`. The way that R2 is defined, you can either produce `01` for [0, inf) times, or `10` for [0, inf) times. There is no modifier outside of both of these statements like R1 has, so you can only produce either `(01)*` or `(10)*`. The outer `( )` on R2 might be confusing you into thinking otherwise, but those parens don't modify R2 in any way (i.e. they could be removed without changing its definition). – ajp15243 Dec 06 '13 at 14:09
  • thanks, got it. the outer () did confuse me – Rave Dec 06 '13 at 15:11