Will it be a^{n}b^{m}..??

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

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

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

Which one of the following is CORRECT?

- Only I
- Only II
- Both I and II
- Neither I nor II

+33 votes

Best answer

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

- 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 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,939 questions

45,453 answers

131,194 comments

48,209 users