The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.4k views

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?

  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II
asked in Theory of Computation by Veteran (103k points)
edited by | 1.4k views

2 Answers

+34 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.

answered by Active (2.1k points)
edited by
+2

Will it be anbm..??

0
yeah
0 votes
Answer only 1
answered by Loyal (8.5k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,053 questions
47,651 answers
147,206 comments
62,380 users