Meaning / proof of these regex

Question

I came across following excerpts while reading about regular expressions identities:

The regex associative laws are: $$(L+M)+N=L+(M+N)$$ $$(LM)N=L(MN)$$ Some important implications out of associative laws are: $$r(sr)^*=(rs)^*r$$ $$(rs+r)^*r=r(sr+r)^*$$ $$s(rs+s)^*r=(sr+s)^*sr$$ $$(LM)^*N*\neq L*(MN)*$$

The issue is that

• I don't find the implications much intuitive as the identities themselves are. How can I understand the implications intuitively? I can always form a strings belonging to left hand side regex and check whether it can be accepted by other regex. The first implication is very simple to test this way. However how can I make them more intuitive??
• Are these implications simply made up expressions which are tested rigorously to hold true and they don't have any specific expression as we can form many such expressions?
• I am unable to get the point behind stating these implications. I dont think of any problem in which I can use these regexes straight / immediately. It may be because I am not able to get intuition behind these implications so that it may strike in my head immediately when to use these implications.

Answer 1

For all three of your statements, the answer is that, generally speaking, the implications simply aren't as intuitive as, say, the associative laws. Look at the analogous problem with algebraic expressions: we have associative laws for addition and multiplication and we also have a distributive law that states that for any expressions $p,q,r$ we have $$ p\cdot(q+r)=(p\cdot q)+(p\cdot r) $$ Eventually, these rules should be intuitively obvious. However, one implication of these rules, that $$ (p+q)^3=p^3+3p^2q+3pq^2+q^3 $$ is probably not as intuitively obvious as the rules used to derive that identity. The utility of the result above is that it can be used as a tool to simplify other more complicated problems.

It's the same for regular expressions: the fact that, say, $r(sr)^*=(rs)^*r$, is correct can be proven rigorously, but having done that you can use it as a tool to show that $$ aa+(aab)^*aa=aa+aa(baa)^*=aa(\epsilon+(baa)^*) $$ should you ever need to. For example, there is a handy technique, involving what's known as Arden's lemma that can be used to produce a regular expression describing the language accepted by a finite automaton. Depending on how it's applied, this can produce several regular expressions from the same FA, so it might fall to you to show that the expressions are indeed equivalent, in which case the "implications" you listed might be handy.

The upshot (here's the tl;dr part), is that the implications you mentioned are simply tools you can use when needed: they've beed proven to hold, but there's no reason why they should be intuitively obvious.