it will be regular.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

$L_1$ =${a^nb^nc^n|n\geq 2}$

$L_2$=${a^nb^mc^k|n,m,k\geq 0}$

$L_3$=$L_1.(L_2)^*$ ,then $L_3$ is

- Regular
- CFL
- Csl
- None

+1 vote

Best answer

$L_3 = L_1(L_2)^*$

So, We can write $L_3$ in the following way :

$L_3 = L_1(L_2^0 + L_2^1 + L_2^2 + ...)$

$L_3 = L_1(\left \{ \in \right \} + L_2 + L_2.L_2 + L_2.L_2.L_2 + ...)$

$L_3 = ( L_1 + L_1.L_2 + L_1.L_2.L_2 + L_1.L_2.L_2.L_2 + ...)$

Now, Because in $L_1$, $n$ is greater than $1$. $L_1$ can't have null string and which makes all the strings of the language $L_3$ starting with $a^nb^nc^n$ where $n \geq 1$ Which makes $L_3$ CSL because whatever logic we apply for $L_3$, We have to parse $a^nb^nc^n$ before proceeding further in the string.

Hence, $L_3$ is $CSL$.

Note that if $L_1$ had contained $\in$ i.e. if $n \geq 0$ then $L_3$ will be Regular. Moreover, in that case $L_3$ would be $\Sigma^*$.

0 votes

L2 is regular as it has no restriction. L1 is CSL as it has double comparison, Now, L3=CSL.Regular(push up). L3=CSL.CSL. CSL is closed under concatenation. Hence L3 is CSL.

0

It's not the case everytime that CSL.CSL=regular because every regular is CSL but some CSL's are not regular so we can't comment about it unless we know, that particular CSL is regular or not. It totally depends on the language and yes if regular is possible then strong answer will be regular not CSL. But here answer is surely CSL.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- 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 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,084 questions

45,575 answers

132,084 comments

49,063 users