CODEWITHSUNDEEP
regular-languagecomputation-theory
webiondev
webiondev

Reputation: 135

When union and concatenation gives same regular expression

{w∈{0,1}∗|w contains exactly one occurrence of 01}

I get the result by both union and concatenation

1*0*011*0*

OR

(1* U 0*)01(1* U 0*)

how come?

Upvotes: 1

Views: 369

Answers (1)

Patrick87
Patrick87

Reputation: 28292

Your two regular expressions are not equivalent. The first one is correct, and the second one is not. To see the difference, use the distributive property of concatenation:

r1 = 1*0*011*0*

r2 = (1* U 0*)01(1* U 0*)
   = 1*011* U 1*010* U 0*011* U 0*010*

Note that r2 is the union of four subexpressions which each describes a language. Each of the described languages is a subset of the language of r1:

1*0*011*0*    1*0*011*0*    1*0*011*0*    1*0*011*0*    
1*  011*      1*  01  0*      0*011*        0*01  1*

Therefore, L(r2) is a subset of L(r1). It has already been pointed out in the comments that L(r1) is not a subset of L(r2), by counterexample (consider string 0110).

To see that r2 is correct, first note that any string in L(r2) is in your language (the only occurrence of 01 is in the middle of the expression, and the expression has to generate it), then argue that any string with exactly one 01 must be generated by this expression. An inductive argument is straightforward and is left as an exercise.

Upvotes: 1

Related Questions