# Does closure under union and concatenation imply closure under Kleene star? [duplicate]

For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The only thing that the latter seems not able to produce is an empty string.

## marked as duplicate by David Richerby, fade2black, Evil, Andrej Bauer, Kyle JonesDec 19 '17 at 4:53

You haven't stated whether you're interested in finite or infinite union, though as you mention, it doesn't really matter due to problem with the empty string. However, instead of giving the answer, let me explain how to answer such questions.

Showing that a language class is closed under operation $O$ given that it is closed under operations $O_1,\ldots,O_m$. You show how to simulate $O$ using $O_1,\ldots,O_m$. For example, suppose that a language class is closed under union and complement. Then it is also closed under intersection, since $A \cap B = \overline{\overline{A} \cup \overline{B}}$.

Showing that if a language class is closed under $O_1,\ldots,O_m$ then it is not necessarily closed under $O$. You given a language class which is closed under $O_1,\ldots,O_m$ but not under $O$. For example, let us show that a language class which is closed under finite union isn't necessarily closed under infinite union. Consider the language class consisting of all finite languages. This class is closed under finite union but not under infinite union.

As an example subset of decidable languages which is closed under both union and concatenation, but not under Kleene star, consider: $\{ \emptyset \}$
$\emptyset \cup \emptyset = \emptyset$
$\emptyset\emptyset = \emptyset$
$\emptyset^* = \{ \epsilon \}$, which doesn't belong to our subset.