0
$\begingroup$

If $L_1 = \emptyset$ , $L_2= \{a\}$ then what is $$L_1\cdot L_2^* \cup L_1^*$$

The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$. My Approach :
$L_1^* = \{\epsilon\}$
$L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* \cup L_1^* = \{\epsilon,a\}$.

Where's my mistake?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The mistake is in $L_2^*$, which is infite: $L_2^* =\{a^n\mid n\in \mathbb N\}$. Also, another mistake is in the final part. For any language $L$, $\emptyset\cdot L=\emptyset$. $\endgroup$
    – R B
    Commented Dec 21, 2014 at 15:01
  • $\begingroup$ Got my mistake ... Please post the same comment as Answer.. would like to mark it as answer $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 15:08
  • $\begingroup$ $L_1\cdot L_2^* = \emptyset \cdot L_2^* = \emptyset$ And thus $L_1\cdot L_2^*\cdot L_1^* = \emptyset \cdot L_1^*= \emptyset$. $\endgroup$
    – R B
    Commented Dec 21, 2014 at 15:08

2 Answers 2

Reset to default
2
$\begingroup$

For any language $L$, $$\emptyset⋅L=\emptyset$$.

Therefore, $$L_1\cdot L_2^* = \emptyset \cdot L_2^* = \emptyset$$

And thus $$L_1\cdot L_2^*\cup L_1^* = \emptyset \cup L_1^*= L_1^* = \{\epsilon\}$$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I meant question is L1⋅L∗2 U L∗1 and not L1⋅L∗2⋅L∗1.. ans will be set of empty set.. and not empty set... $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 15:14
  • $\begingroup$ kindly edit ur solution accodingly.. so that i can mark it as solution. $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 15:14
  • $\begingroup$ Could you please write it in Latex? I'm having hard times reading your comments (not sure what you mean). $\endgroup$
    – R B
    Commented Dec 21, 2014 at 15:15
  • $\begingroup$ something else.. $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 15:16
2
$\begingroup$

Your problem is in applying the definitions of the concatenation and Kleene-star operators. The exercise was probably deliberately chosen to test your understanding of the difference between $\emptyset$ (the language containing no strings at all) and $\{\epsilon\}$ (the langauge containing only the empty string), and how the operators apply to them, but you also tripped up on $\{a\}^*\!$.

  • For any language $L$, $L^*$ is the language formed by taking zero or more strings from $L$ and concatenating them. In particular, if $L=\emptyset$, the only way that you can choose zero or more strings from $L$ is to choose none. If you start with no characters and concatenate nothing, you still have no characters: the empty string. So $L_1^* = \emptyset^* = \{\epsilon\}$. On the other hand, if you start with $L_2=\{a\}$ and choose zero or more strings from that language, you have chosen zero or more $a$s. Therefore, $L_2^* = \{a^n\mid n\geq 0\} = \{\epsilon, a, aa, aaa, \dots\}$.

  • For any languages $L$ and $L'\!$, $L\cdot L'$ is the set of all strings that can be made by choosing one string from $L$ and one from $L'$ and concatenating them. You can never choose a string from the empty language, so you can never make any strings by concatenating something in $\emptyset$ and something in $L2^*$, so $L_1\cdot L_2^* = \emptyset\cdot L_2^* = \emptyset$.

So the answer is $\emptyset \cup \{\epsilon\} = \epsilon$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am tempted to mark ur ans as the best solution but since the previous ans was also precise and quick response to my query i am keeping it as final ans.. $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 17:03
  • $\begingroup$ Thanks for such a beautiful explanation and soorry that i am not marking it as final ans .. thanks a lot.. :) $\endgroup$
    – Jay Teli
    Commented Dec 21, 2014 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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