5.7k views

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\}$

edited | 5.7k views
+1

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

+1

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$## 5 Answers +60 votes Best answer Concatenation of empty language with any language will give the empty language and${L_1}^ * = \phi^* = \epsilon$. Therefore,$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 0 @csegate2$\epsilon = \{\epsilon\}$only when the right side is language and left side is regular expression. +1 How is it possible that concatenation of Φ With anything gives Φ (as ab.Φ= Φ) but concatenation of Φ With Φ gives ∈ (as Φ*= ∈)? (for eg. ΦΦΦ*) how?? +29$\phi $concatenated with$\phi$gives$\phi$. But$\phi^* = \epsilon$as$^*$includes "0" repetition. This is like multiplying by "0".$\phi^* = \epsilon, \phi^+ = \phi.$0 Why null union epsilon = epsilon ? +9 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? 0 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. +6 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. +1 Thanks. Always used to confuse between null and epsilon but now somewhat they are clear. +1 @Arjun Suresh Sir, Why phi concatenated with anything is phi... Should not it be that string which is concatenated with phi?? +1 When you multiply anything with 0, what we get? Such things are defined by the operation. +1 Ok Sir.. Thanks.. One more query: Does phi concatenated with a string and a string concatenated with phi both give the result phi? +1 yes. 0 ∅* = ∊ bcoz * is zero or more (can be 0) and epsilon(∊) is a 0 - length string, + = ∅ bcoz + can not be zero. +1 What is the difference between$\phi \cap L$and$ \phi . L$? i.e. intersection and concatenation. please give an example. +1 @Satbir there is no difference between$\phi \cap L$and$\phi . L\$

but there is difference between intersection and concatenation.

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

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

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

L1=ϕ

L2*=a*

L1*=ϕ* = ∊

L2*L1*=a*

L1L2*L1*=ϕ.a*=ϕ

+1
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

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

by Active
0
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