1
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Please sort your thoughts before posting and formulate one question per post. In fact, I think you are looking for tutoring, which this platform works badly for. It would be best to get in a room with a teacher. $\endgroup$ – Raphael Nov 12 '16 at 20:30
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yess this is quite satisfying and shows up a level of maturity. Sometimes we are more prone to focus on how to prove things theoretically, instead of trying to internalize it based on some intuition so that it can be used in actual practice. My effort with this question was to do so and you just taught me what we use in practice may not be immediately intuitive but still we have to use it. I can relate this with other formulae too. Should be quite obvious to me, but we less frequently deal regex simplifications. So why the question seem to arise in my head. $\endgroup$ – anir Nov 13 '16 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.