The Gateway to Computer Science Excellence
+34 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\}$
in Theory of Computation by Veteran
edited by | 5.7k views

Approach to solve such problem is to follow  precedence and associativity​​​​​​​.

precedence closure>concatenation​​​​​​​>union

then associative  

concatenation​​​​​​​ ::Left to right

union ::Left to right

if you perform any anything other than this option a ,and option c may come


Why $\phi ^*=\epsilon\ ?$ (Some comment's are there below the Best answer you can go through them also)

Giving one more explanation for better understanding.

$RE\rightarrow \epsilon-NFA$ (Thomson construction algorithm)

1. How to make $\epsilon-NFA$ for $\phi:$

2. How to make $\epsilon-NFA$ for $a^*:$

3. How to make $\epsilon-NFA$ for $\phi^*:$ Just remove a from the above diagram.

Hence proved $\phi^*=\epsilon$

Note: $ \$=\epsilon$

Ref: Thomson's construction

5 Answers

+60 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\}$. 

by Veteran
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.

What is the difference between $\phi \cap L$ and $ \phi . L$ ? i.e. intersection and concatenation. please give an example.

@Satbir there is no difference between $\phi \cap L$ and $\phi . L$ 

but there is difference between intersection and concatenation. 

+5 votes
L1.anything is empty language and empty union empty* is epsilon hence a
by Active

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

+5 votes

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

Answer is A

by Active
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.
by Boss
0 votes
the correct option is (A)

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
52,223 questions
59,811 answers
118,087 users