Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

  • $\begingroup$ They are equivalent because both accept exactly "a string of at least one a", but for educational purposes it would be interesting to see a formal proof, which I can't produce. $\endgroup$ – Albert Hendriks Mar 17 '19 at 14:03
  • $\begingroup$ me neither, that's why I am not sure $\endgroup$ – Yamahari Mar 17 '19 at 14:04
  • $\begingroup$ You can prove it directly on the regular expressions: Let $w \in L(aa^\ast)$, i.e. $w = a \cdot u$ with $u \in L(a^\ast)$, i.e. $u = a^k$. for some $k \in \mathbb{N}$. Then $w = a^{k+1} = a^k a \in L(a^\ast a)$. The other direction is analogous. However, for these simple expression you might also want to compute the corresponding NFAs and transform them to the minimal DFAs. If these DFAs coincide the regexes have also to be equivalent. $\endgroup$ – ttnick Mar 17 '19 at 14:57
  • 1
    $\begingroup$ "Even though concatenation is not commutative" The reason the equality holds seems to be associativity of concatenation instead. $(\underbrace{a \cdot \ldots \cdot a}_{k}) \cdot a = a \cdot (\underbrace{a \cdot \ldots \cdot a}_{k})$, for every fixed $k$. $\endgroup$ – Hendrik Jan Mar 17 '19 at 20:46
  • 1
    $\begingroup$ For three words $x,y,z$ such that $xy = yz$, we have $x^*y=y^*z$. This is called the bisimulation rule. $\endgroup$ – John L. Mar 17 '19 at 21:03

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1\dots w_\ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1\dots w_d$ matches $R$ and $w_{d+1}\dots w_\ell$ matches $S$. Here, $d=0$ and $d=\ell$ mean that we've split $w$ into $\varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1\dots w_\ell$ such that, for some $d$, $w_1\dots w_d$ matches $a^*$ and $w_{d+1}\dots w_\ell$ matches $a$. We must have $d=\ell-1$ and $w_\ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w_1=\dots=w_{\ell-1}=a$ because that is the only length-$(\ell-1)$ string that matches $a^*$. So $w=a^{\ell}$ for some $\ell\geq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^{\ell}$ for some $\ell\geq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^\ell$ for $\ell\geq 0$, and $a$ matches the single string $a=a^1$. So $a^*a$ matches any string $a^\ell a$ for $\ell\geq 0$, i.e., any string $a^{\ell+1}$ for $\ell\geq 0$, i.e., any string $a^\ell$ for $\ell>0$. Similarly, $aa^*$ matches any string $aa^\ell=a^{1+\ell}$ for $\ell\geq 0$, i.e., $a^\ell$ for $\ell>0$.


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.