1
$\begingroup$

I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$):

  • $(a^*+bb^*)^*$
  • $(a^*b+b^*a)^*$
  • $(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$

I want to generalise different ways in which we can append to original regular expression $(a+b)^*$, to not to change its meaning and still get set of all strings on alphabet $\{a, b\}$. I think we can do this in two ways :

  • P1: We can concatenate anything to $a$ and $b$ inside brackets of $(a+b)^*$
  • P2: We can concatenate $(a+b)^*$ with any regular expression which has star at most outer level ($(...)^*$)

  • P3: I know $(a+b)^* = (a^*+b)^* = (a+b^*)^*= (a^*+b^*)^*$. So I guess P1 and P2 also applies to them.

Am I correct with P's?

Q. Also I know $(a+b)^*=(a^*b^*)^*=b^*(a^*b)^*=(ab^*)^*a^*$. Can we append some pattern of regular expressions to these also to not to change their original meaning?

$\endgroup$
  • $\begingroup$ You might be interested in axiomatizations for the equational theory of regular expressions (such as the two famous one due to Salomaa). These enable you to prove the equivalence of any two regular expressions. $\endgroup$ – Yuval Filmus Nov 21 '19 at 12:23
  • 1
    $\begingroup$ Let $\Sigma=\{a,b\}$. Since you're only talking about concatenation, if $A$ is a regular expression such that $L(A) = \Sigma^*$ (i.e., $A$ is equivalent to $(a+b)^*$) and $B$ is another regular expression, then $L(AB) = \Sigma^*$ if and only if $B$ matches the empty string $\epsilon$. The "if" direction is trivial since $\Sigma^* = L(A) \subseteq L(AB) \subseteq \Sigma^*$. The "only if" direction follows from the fact that $\epsilon \in L(A) \setminus L(B) \subseteq L(A) \setminus L(AB)$ which implies that $L(A) \setminus L(AB) \neq \emptyset$, i.e., $L(A)$ and $L(AB)$ differ. $\endgroup$ – Steven Nov 21 '19 at 12:33
  • $\begingroup$ Just to clarify my previous comment: in the "if" direction I'm assuming that $\epsilon \in L(B)$, while in the "only if" direction I'm assuming that $\epsilon \not\in L(B)$. $\endgroup$ – Steven Nov 21 '19 at 14:08
  • $\begingroup$ Q1. You said "...if and only if $B$ matches the empty string $ϵ$...". Isnt it same as what I said in P2 "...any regular expression which has star at most outer level ($(...)^∗$)..."? Does that mean P2 is correct? Q2. I did not get $\epsilon \in L(A)\setminus L(B)\subseteq L(A)\setminus L(AB)$. Do you mean left quotient by $\setminus$? Isnt $L(A)\setminus L(AB)=L(B)$. Similarly $L(A)\setminus L(B)=L(B)$ if $\epsilon\in L(A)$, right? If yes, then isnt $L(A)\setminus L(B)=L(A)\setminus L(AB)=L(B)$? $\endgroup$ – anir Nov 23 '19 at 10:01

Your Answer

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

Browse other questions tagged or ask your own question.