The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
65 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
asked in Theory of Computation by Loyal (6.4k points)
edited by | 65 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.

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 (18.7k points)
edited by
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.  

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 (267 points)
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.


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

40,851 questions
47,514 answers
145,842 comments
62,274 users