The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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

  1. Regular
  2. CFL
  3. Csl
  4. None
asked in Theory of Computation by Loyal (9.3k points)
edited by | 70 views
Look in L1 n>=2
$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)


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

2 Answers

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

answered by Boss (21.8k points)
edited by
If L3 had contained $\varepsilon$ how L3 would have been regular infact $\sum *$ ?

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

Typo Brother. Corrected now.  

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.
answered by (275 points)
you cannot give this logic that

$\text{CSL .CSL}=CSL$

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

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


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.

Related questions

0 votes
1 answer
asked Dec 14, 2017 in Theory of Computation by irfan_ (11 points) | 128 views
0 votes
0 answers

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

47,139 questions
51,386 answers
66,699 users