Is (a|b)* the same as a*|b*?

Question

Is (a|b)* the same as a*|b*? In other words, does (a|b)* accept string which are combinations of as and bs?

Thurmond

I'm Mr. Meeseeks, look at meee! – Slowworm

@meeseeks wubalubadubdub!!! – Thurmond

Answer 1

Is (a|b)* the same as a*|b*?

They are not the same.

• a*|b* means "(0 or more as) or (0 or more bs)"

• (a|b)* means "0 or more (a or b)s"

So, for example, ab will be matched by (a|b)* but not by a*|b*. Note also that anything matched by a*|b* will also be matched by (a|b)*.

Dionysus

Answer 2

No.

In case of (a|b)*, you can mix As and Bs (see demo).

In case of a*|b*, you can have either As or Bs (see demo).

Lindo

Answer 3

a*|b* denotes {ε, "a", "b", "aa", "bb", "aaa", "bbb", ...}

(a|b)* denotes {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", aab, abb, aba, baa ...}

ε denote empty

Bobseine