Regular Expressions: is $a^*a = a^*$

91 Views Asked by At

I am practicing simplifying regular expressions. In the list of 12 regular expression identities outlines in this video, I see among them

$AA^*=A^*A$

$ϵ + AA^* = ϵ + A^*A = A^*$

Why do you have to "or" $AA^*$ with the empty string in order for it to equal $A^*$ ?

Why isnt $AA^* = A^*$ ?

@Wojowu commented, very helpfully, that $AA^* \neq A^*$ because $A^*$ necessarily contains the empty string, while $AA^*$ does not.

However, if A does contain the empty string,ie $A = ϵ + C$, then does $AA^* = A^*$ ?

2

There are 2 best solutions below

0
On BEST ANSWER

$a^*$ stands for zero or more repetitions of $a$. You have at least one copy of $a$ in every string in the language $a^*a$, so they are not equivalent.

0
On

So your question is

$$(\epsilon+C)(\epsilon+C)^*\stackrel?=(\epsilon+C)^*.$$

Indeed, you can rewrite as

$$\epsilon(\epsilon+C)^*+C(\epsilon+C)^*=(\epsilon+C)^*+C(\epsilon+C)^*.$$