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.

  • 3
    $\begingroup$ 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. $\endgroup$ – G. Bach Jan 18 '14 at 19:40
  • 1
    $\begingroup$ @G.Bach: Somehow I think the exercise got copied down wrongly... $\endgroup$ – Raphael Jan 18 '14 at 19:43
  • $\begingroup$ "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. $\endgroup$ – Raphael Jan 18 '14 at 19:43
  • $\begingroup$ @Raphael: I made it exactly the way the exercise was written in the paper. $\endgroup$ – Joudicek Jouda Jan 18 '14 at 21:03
  • $\begingroup$ Hint: $L^*$ is never empty. $\endgroup$ – Yuval Filmus Jan 18 '14 at 21:31

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


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.