The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+25 votes

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

- $\{\epsilon\}$
- $\phi$
- $a^*$
- $\{\epsilon, a\}$

+40 votes

Best answer

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

*T**herefore,*

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

0

@csegate2 $\epsilon = \{\epsilon\}$ only when the right side is language and left side is regular expression.

0

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

(for eg. ΦΦΦ^{*}= ∈) how??

+15

$\phi $ concatenated with $\phi$ gives $\phi$. But $\phi^* = \epsilon$ as $^*$ includes "0" repetition. This is like multiplying by "0". $\phi^* = \epsilon, \phi^+ = \phi.$

+2

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.

So overall bag B1 have one empty bag and another bag with empty purse. Thus B1 has contents in it, although they are empty.

+3

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.

+1

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

+4 votes

+4 votes

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,000 questions

45,496 answers

131,569 comments

48,632 users