4
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

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.

Given this information, you should be able to answer your question on your own.

$\endgroup$
4
$\begingroup$

No, it doesn't.

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$
but
$\emptyset^* = \{ \epsilon \}$, which doesn't belong to our subset.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.