GATE CSE 2013 | Question: 8

Question

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

Comments

what would be the ans for:  Φ * ε ?

---

Concatenation of empty language with any language will give empty language

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

Answer 1

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

Comments

@halfcodeblood,

If union has grater precedence than concatenation then answer is phi. But as we know, union has less precedence than concatenation,  answer is language which contains empty string.

---

Ok now clear.

Thanks.

---

what would be the ans for:  Φ * ε ?

Answer 2

L1.anything is empty language and empty union empty* is epsilon hence a

Comments

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*=ϕ

 

---

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

Answer 3

Answer is A

Comments

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

Answer 4

Should be A as per me.

Answer 5

the correct option is (A)