2
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ No. If you start with a collection of finite languages, you cannot obtain an infinite language by union and concatenation. $\endgroup$ – Tunococ Sep 6 '13 at 9:58
  • 3
    $\begingroup$ Also, if you start with a collection of language not containing $\epsilon$, you cannot obtain a language containing $\epsilon$ by union and concatenation. $\endgroup$ – Hagen von Eitzen Sep 6 '13 at 11:10
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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