The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 votes

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

(A) $\{\epsilon\}$

(B) $\phi$

(C) $a^*$

(D) $\{\epsilon, a\}$

(A) $\{\epsilon\}$

(B) $\phi$

(C) $a^*$

(D) $\{\epsilon, a\}$

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

@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.$

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.

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.

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

@Arjun Suresh Sir, Why phi concatenated with anything is phi... Should not it be that string which is concatenated with phi??

+3 votes

+1 vote

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,705 questions

40,252 answers

114,340 comments

38,861 users