I have the following 4 claims about languages. I need to state whether each is true/false and provide a short justification.

  1. $\forall L : (L^+)^* = L^*$
  2. $\forall L_1, L_2 : (L_1 = L_2 \iff L^*_1 = L^*_2)$
  3. $\forall L_1, L_2 : L_1 L_1^* L_2 \subseteq L_1^* L_2$
  4. $\forall L_1, L_2 : L_1^* L_2 \subseteq L_1 L_1^* L_2$

Progress so far:

First I begin with a selection of definitions provided by my reference literature:

  • Alphabet "$\sum$": A non empty finite set.
  • Symbol: An element from an alphabet.
  • Word: a finite sequence of symbols from an alphabet.
  • Empty word ($\varepsilon$): A sequence consisting of 0 symbols.
  • Language ($L$): A subset from $\sum^*$
  • $L^* = \bigcup_{i \geq 0} L^i$
  • $L^+ = \bigcup_{i \geq 1} L^i$

Attempts at solutions:

  1. I have found a solution which claims true because $L^* = L^+ \cup \{ \varepsilon \}$. Perhaps someone could elaborate here? I interpret the question to mean that we first we take the union of all words $\geq 1$ and then the union of all worlds $\geq 0$, i.e I first compute the term inside the brackets before I compute the outer $*$. Am I making an error here?
  2. I have a solution which claims that this is false by providing the counter example $\forall w \in L_1 : w \in L_2 \land \forall w \in L_2 : w \in L_1, L_1 = \{ a , b \}, L_2 = \{ a , b, a, b \}$. I thought that it was against the rules to define duplicate items in a set? I don't understand the idea here.

For the remaining solutions I have not made any progress.


$L \subseteq L^+$ so $L^\ast \subseteq (L^+)^\ast$.

The reverse is also true: if $x$ is a word in $(L^+)^\ast$, it is either equal to $\varepsilon$ which is also in $L^\ast$, or $x= w_1w_2 \cdots w_n$ where all $w_i$ are from $L^+$, so themselves concatenations of some finite number of words from $L$. So that makes $x$ of the same form, hence in $L^\ast$.

Check that $L_1 = \{0,1,00\}$ and $L_2 = \{0,1,10\}$ obey $L_1^\ast = L_2^\ast$.

3 is true as $L_1L_1^\ast \subseteq L_1^\ast$ already. Quite trivial to check.

  1. $L_1 =\{0\}$ and $L_2 = \{1\}$ is a counterexample as $1$ is in the left language but not in the right one.

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.