The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ?

  1. $\{\epsilon\}$
  2. $\phi$
  3. $a^*$
  4. $\{\epsilon, a\}$
asked in Theory of Computation by Veteran (368k points)
edited by | 3.8k views

5 Answers

+44 votes
Best answer

Concatenation of empty language with any language will give the empty language and ${L_1}^ * = \phi^* = \epsilon$.


$L_1L_2^* \cup L_1^*   $
$=\phi.(L_2)^* \cup \phi^ *$
$= \phi \cup \{\epsilon\} \left(\because \phi \text{ concatenated with anything is } \phi \text{ and }\phi^* = \{\epsilon\} \right)  $
$= \{\epsilon \} $.

Hence, option (A) is true.

PS: $\phi^* = \epsilon$, where $\epsilon$ is the regular expression and the language it generates is $\{\epsilon\}$. 

answered by Veteran (55.4k points)
edited by
@csegate2 $\epsilon = \{\epsilon\}$ only when the right side is language and left side is regular expression.

How is it possible that concatenation of  Φ With anything gives  Φ (as ab.Φ= Φ) but concatenation of  Φ With Φ gives ∈  (as Φ*= ∈)?

(for eg. ΦΦΦ*) how??

$\phi $ concatenated with $\phi$ gives $\phi$. But $\phi^* = \epsilon$ as $^*$ includes "0" repetition. This is like multiplying by "0". $\phi^* = \epsilon, \phi^+ = \phi.$
Why null union epsilon = epsilon ?
You have an empty bag and another bag with an empty purse. Now you put their contents into a single bag. What will you get?
Meaning there is a bag B1 which has other two bags B11 and B12. B11 is empty and B12 has another empty purse P1 in it.

So overall bag B1 have one empty bag and another bag with empty purse. Thus B1 has contents in it, although they are empty.
No, I told to put "their contents" not "them" into the new bag. So, B1 will have an empty purse in it.

Now, replace the purse by strings and bags by the set of strings -- languages. So, the union will have an empty string.

Always used to confuse between null and epsilon but now somewhat they are clear.
@Arjun Suresh Sir, Why phi concatenated with anything is phi... Should not it be that string which is concatenated with phi??
When you multiply anything with 0, what we get? Such things are defined by the operation.
Ok Sir.. Thanks.. One more query: Does phi concatenated with a string and a string concatenated with phi both give the result phi?

∅* = ∊ bcoz  *  is zero or more (can be 0) and epsilon(∊) is a 0 - length string,

+ = ∅ bcoz + can not be zero.

+4 votes
L1.anything is empty language and empty union empty* is epsilon hence a
answered by Active (1.2k points)

Closure has the highest precedence, followed by concatenation, followed by union.

otherwise we will get a wrong answer as shown below ;)



L1*=ϕ* = ∊ 



Operator Symbol Precedence Position Associativity
Kleene star * 1 Postfix Associative
Concatenation N/A 2 Infix Left-associative
Alternation | 3 Infix Left-associative

someone explain this with example pls

+4 votes

L_1L_2^* = \phi \because \text{ concantenation of any language with } \phi \text{ gives } \phi. \phi^* = \epsilon

Answer is A

answered by Active (4.2k points)
Why are we considering L1.L2*  = phi  as 0*a=0 but why not phi concatenated with multiple a so product becomes a* and final equation becomes a union epsilon
+1 vote
Should be A as per me.
answered by Boss (19.9k points)
–1 vote
the correct option is (A)
answered by (325 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,254 questions
49,750 answers
65,847 users