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

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

---

https://math.stackexchange.com/questions/472952/understanding-concatenating-the-empty-set-to-any-set

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

@Shaik Masthan sir please explain little bit more about the significance of precedence and associativity in the context of this question.

Thanks

---

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

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.