# Thread: Automata theory, regular expressions

1. ## Automata theory, regular expressions

Hi,
I'm having trouble with constructing proof for the following assertions:

R + S = S + R , commutativity

(R + S) + T = R + (S + T)
R (ST) = (RS) T, associativity

(R+S)T = RT + ST, distributivity

Where R,S,T are regular expressions. + is the union operation and when there is no operator it indicates concatenation.

Can anyone give me some guidance?

2. ## Re: Automata theory, regular expressions

This all follows directly from the definition of when a string matches a regular expression. You should consult the precise definition in your source; i'll go from memory. For example, suppose a string w matches (R + S)T. Then w = w1w2 such that w1 matches R + S and w2 matches T. This in turn means that w1 matches either R or S. In the first case, w1w2 matches RT, and in the second case, it matches ST; therefore, w = w1w2 matches RT + ST. Other questions are similar.

3. ## Re: Automata theory, regular expressions

Thank you. I'll try to figure the rest ones out.
Although R + S = S + R , commutativity, is still not clear to me. I think that this one can't be proven with your method.

4. ## Re: Automata theory, regular expressions

If w matches R + S, then by definition it matches either R or S. In both cases it matches S + R.