GATE CSE 2014 Set 2 | Question: 15

Question

If $L_1\:=\{a^n \mid n\:\geq\:0\}$  and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider 

1. $L_1.L_2$ is a regular language
2. $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$

Which one of the following is CORRECT?

• A. Only I
• B. Only II
• C. Both I and II
• D. Neither I nor II

Comments

tricky question

max chance of wrong answer though you know concept

---

The language($L$) generated by concatenation of $L_1$ and $L_2$ is

$L = L_1.L_2 = \{a^nb^m \mid n,m\: \geq \:0\}$

---

tricky one!

Answer 1

Option A.

$L_1 = \{ \varepsilon, a, aa, aaa, aaaa, \ldots \}$

$L_2 = \{ \varepsilon, b, bb, bbb, bbbb, \ldots \}$

$\begin{align}
L_1 \cdot L_2 &= \left \{ \begin{array}{c} \varepsilon , \\ a, &b,\\ aa, &ab, &bb\\ aaa, &aab, &abb, &bbb,\\ aaaa, &aaab, &aabb, &abbb, &bbbb, & \ldots \end{array}\right \}\\[1em]
L_1 \cdot L_2 &= a^*b^*
\end{align}$

Thus, $L_1 \cdot L_2$ is Regular.

(Also, since both $L_1$ and $L_2$ are Regular, their concatenation has to be Regular since Regular languages are closed under concatenation)

However, $L_1 \cdot L_2 \neq a^nb^n$. This is because in $a^*b^*$, the number of $a$'s and $b$'s can be different whereas in $a^nb^n$ they have to be the same.

Comments

Will it be aⁿb^m..??

---

yeah

---

But in a question given a^n and b^n so why a^n and b^m ???

Please explain me Option 1 how it is correct because in option 1 and option 2 both have concatenation ??

---

See the possibilities we get after concatenation of L1 and L2.

“But in a question given a^n and b^n so why a^n and b^m ???” We considered a^n and b^m because both L1 and L2 are given explicitly, that means we can have any number of a’s followed by any no of b’s. So, it is regular.

If the question asked L = a^n.b^n, then only we have restrictive case.

 

Answer 2

L1.L2 is also regular since regular languages are closed under concatenation.

But, L1.L2 is not { anbn | n ≥ 0 }, because both the variable is independent in both languages.
It should have been L1.L2 = { ambn | m ≥ 0, n ≥ 0 }

So, the correct answer is option (A).

Answer 3

Answer only 1