Given any two languages $A$ and $B$, recall the following regular operations:
- Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$
- Concatenation: $A \circ B = \{xy \mid x \in A \text{ and } y \in B\}$
- Star:
$$A^* = \bigcup_{k=0}^\infty A^k$$
where $A^0 = \{\varepsilon\}$ and for all $k\geq0$, $A^{k+1} = A^k \circ A$.
It is well-known that the class of all regular languages is closed under these three operations. But let's forget that for a second and assume that we only know that the class of all regular languages is closed under the union and concatenation operations. Using these two facts together with induction, can we infer that the class of all regular languages is also closed under the star operation (without explicitly constructing some finite automaton that recognizes $A^*$)? I thought it might work at first, but upon further reflection, I'm having some doubts (the infinity sign is messing with my intuition, I think).
Best Answer
No, you can't. As an example of what goes wrong, observe that the class of finite languages is closed under finite unions and concatenation but not under star, so closure under the first two does not imply closure under the third.