70 views

$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

1. Regular
2. CFL
3. Csl
4. None
edited | 70 views
0
0
Look in L1 n>=2
+1
$L_1=a^{n}b^{n}c^{n},n \geq 2 \text{ is CSL}$

$L_2=a^{n}b^{m}c^{k},n ,m,k \geq 0 \text{ is regular}$

$\text{regular exp }=a^{*}b^{*}c^{*}$

$(L_2 )^{*}=(a^{*}b^{*}c^{*})^{*}$   is regular (hence CSL)

so,

$a^{n}b^{n}c^{n} .(a^{*}b^{*}c^{*})^{*}$ will be CSL , as  $L_1$ can never be empty.

+1 vote

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

edited
0
If L3 had contained $\varepsilon$ how L3 would have been regular infact $\sum *$ ?
+1

If L3 had contained εε how L3 would have been regular infact ∑∗∑∗ ?

Typo Brother. Corrected now.

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
you cannot give this logic that

$\text{CSL .CSL}=CSL$

$\text{CSL .CSL=regular is possible}$
0
Of course, All Regulars are CSL. So strong answer is CSL.
+1
If regular possible then strong answer will be regular ,,csl will be generalized answer
+1

If regular possible then strong answer will be regular ,,csl will be generalized answer

Right.

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.

+1 vote
1
+1 vote
2