3
$\begingroup$

If $L_1 = Ø$, I read that $L_1^\ast$ is $\{\varepsilon\}$. Why is this so? I am unable to understand this. Can someone please explain? I understand that $Ø$ is an empty string while $\varepsilon$ allows us to make transitions without symbols. But, why is $L_1^\ast$ not $Ø$ and why is it $\{\varepsilon\}$?

$\endgroup$
0

3 Answers 3

4
$\begingroup$

Going back to Kleene star's definition

If $L$ is a set of symbols or characters then $L^*$ is the set of all strings over symbols in $L$, including the empty string $\epsilon$.

In the case $L=\varnothing$, following the definition we get $L^{*} = \{\epsilon\}$

$\endgroup$
3
$\begingroup$

The definition of Kleene star: $$ A^\ast:=\bigcup_{i=0}^n A^n $$ where $A^0=\{\varepsilon\}$ (see, for example, wiki: http://en.wikipedia.org/wiki/Kleene_star). If $A = \emptyset$ then $A^i = \emptyset$ for $i \geq 1$, but $A^0$ is still there.

$\endgroup$
3
$\begingroup$

You say

  • Ø is an empty string - wrong.
  • ε allows us to make transitions without symbols - so what is it?

In fact

  • $\emptyset$ is the empty set.
  • $\epsilon$ is the empty string.

All the strings that can be made with no things (letters or whatever you want to call them) are just one: the empty string.

$\endgroup$
0

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.