Let $L$ be the language defined by the regular expression $(a \vee b \vee c)(a \vee b \vee c)$

Question

1) How does $|L| = 9$?

2) $|L^*| = \aleph_0$?

Thank you

Answer 1

HINTS:

1. Either use the multiplication principle, or write out all words of the language in systematic fashion from the regular expression.

2. If $w\in L$, then $w,ww,www,\ldots\in L^*$. With a little more work you could actually say exactly what the lengths of words in $L^*$ are, and how many of each length there are.

Answer 2

1)
Notice there are two groups with three distinct possibilities each, so $$|L| = 3^2 = 9$$ More specific $$L = \{aa, ab, ac, ba, bb, bc, ca, cb, cc\}\tag{1}$$

---

2)
You want to show that $L^\ast$ is countably infinite. $L^\ast$ is infinite since $|L| > 0$. Now think of how to enumerate the elements of $L^\ast$ given an enumeration for $L$ $$L \stackrel{(1)}\simeq \{1,\ldots, 9\}$$