# If $L^*$ or $L^+$ is empty, can L be an infinite language?

I have to prove or disprove the implications in these two situations

1. $L^* = \emptyset$ $\rightarrow$ $L$ is infinite
2. $L^+ = \emptyset$ $\rightarrow$ $L$ is infinite

Here are my thoughts.

1. I would say Kleene star operation (*) is union of

$\qquad L^0 \cup L^1 \cup L^2 \cup \dots$

and since $\_^0 = \{\epsilon\}$ (even $\emptyset^ 0 = \{\epsilon\}$), there is no language $L$ such that $L^* = \emptyset$.

How to prove finiteness/infiniteness?

2. Only language $L$ where $L^+ = \emptyset$ is $\emptyset$ which is a finite language. But how to prove there is no other language that is inifinite and the argument is valid for it?

EDIT: will it help if I rewrite the implications $A \rightarrow B$ to $\neg B \rightarrow \neg A$ ?

1. $L$ is finite $\rightarrow$ $L^* \neq \emptyset$
2. $L$ is finite $\rightarrow$ $L^+ \neq \emptyset$

2) can be now interpreted as $\emptyset^+ = \{\epsilon\}$ and $\emptyset$ is a finite language. So the implication doesn't work.

• If $L$ is infinite, then there is some $x \in L$. Since $L \subseteq L^*$ and $L \subseteq L^+$, you have $x \in L^*$ and $x \in L^+$, so both are nonempty. That $L$ is infinite isn't even relevant there, it's enough that $L$ is nonempty. – G. Bach Jan 18 '14 at 19:40
• @G.Bach: Somehow I think the exercise got copied down wrongly... – Raphael Jan 18 '14 at 19:43
• "But how to prove there is no other language that is infinite and the argument is valid for it?" -- Pick any and see what happens. – Raphael Jan 18 '14 at 19:43
• @Raphael: I made it exactly the way the exercise was written in the paper. – Joudicek Jouda Jan 18 '14 at 21:03
• Hint: $L^*$ is never empty. – Yuval Filmus Jan 18 '14 at 21:31

## 1 Answer

1) You need to take a look at this page. Remember that there is an implication to be proved true or false.

2) Consider the fact $L \subseteq L^{+}$ and apply it to the case $L^{+} = \emptyset$.