CODEWITHSUNDEEP
regexregular-languagedfa
Andrew Ward
Andrew Ward

Reputation: 25

How does Kleene Star interact with the Union operator?

This question is related to finite automatas and regular expressions. I've come up with a really ugly regex and I'm trying to simplify it.

I understand the idea that (ε U aa*) = {ε} U {a, aa, aaa, ... } = a*

However, I've been unable to find any confirmation that (ε U a*) = a*.

Furthermore, if I have the expression (a U a*), wouldn't it be equivalent to a*?

The latter two statements "seem" obviously true to me, but I'm suspicious, because lecture notes all over the web seem to be pointedly avoiding making these connections, and my textbook (Sipser) doesn't mention any of it.

Upvotes: 0

Views: 883

Answers (1)

Q the Platypus
Q the Platypus

Reputation: 845

Yes (ε U a*) = a* is true.

You can confirm it by the equality you gave and the tautology x U x = x.

Start with (ε U a*) = (ε U (ε U aa*) ) = (ε U ε) U aa* = ε U aa* = a*

Likewise (a U a*) = (a U (ε U aa*)) = (ε U (a U aa*)) then factor = (ε U a(ε U a*)) = (ε U aa*) = a*

Upvotes: 1

Related Questions