2 votes 2 votes if L1 = { anbncn | n>= 0 } and L2 = { anbmck | k,n,m>=0} L1 is CSL and L2 is regular. Now L3 = L1.(L2)*. Is L3 is regualar or CSL? Theory of Computation theory-of-computation context-sensitive regular-language + – AnilGoudar asked May 10, 2017 • retagged Jun 4, 2017 by Arjun AnilGoudar 3.2k views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply Show 14 previous comments Purvi Agrawal commented May 11, 2017 reply Follow Share Yes there exists concatenation but no cross product in toc 0 votes 0 votes Akriti sood commented May 11, 2017 reply Follow Share so sorry,i mixed them..:-P 0 votes 0 votes arun yadav commented Oct 4, 2020 reply Follow Share Is L2 is regular? 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes Regular L1 = { $\epsilon$, abc, aabbcc, ... } L2 = a*b*c* L3 is L1.(L2)*, means $a^nb^nc^n(a^*b^*c^*)^*$ The important thing to notice is that n can be 0. So L3 will be $(a^*b^*c^*)^*$. Which is regular. Dhruv Patel answered May 11, 2017 Dhruv Patel comment Share Follow See all 8 Comments See all 8 8 Comments reply Archies09 commented May 11, 2017 i edited by Archies09 May 11, 2017 reply Follow Share @Dhruv Patel since n is not static ur dfa cannot count number of a's and then match it with b's and c's or you can give a dfa which accepts anbncnabc 0 votes 0 votes Dhruv Patel commented May 11, 2017 reply Follow Share @Archies09 The thing is that we don't have to remember n. Say input string is $a^7b^7c^7aaabbcabcc$ Does it belong to L3? Sure it does. Take $\epsilon$ from L1 concatenate it with $a^7b^7c^7a^3b^2cabc^2$ from L2. 0 votes 0 votes Archies09 commented May 11, 2017 reply Follow Share I missed out on n=0. So language L3 becomes Σ* Hence regular. Thanks for explanation@Dhruv Patel 0 votes 0 votes Dhruv Patel commented May 11, 2017 reply Follow Share @Archies09 L3 is not $\Sigma^*$. It's $(a^*b^*c^*)^*$. 0 votes 0 votes Archies09 commented May 11, 2017 reply Follow Share @Dhruv Patel Can you give me a string which cannot be produced by (a*b*c*)* ?? 0 votes 0 votes Dhruv Patel commented May 11, 2017 reply Follow Share @Archies09 Oh I see it now. Sorry. They are same :) 0 votes 0 votes Harsh181996 commented May 15, 2017 reply Follow Share So , shouldn't the answer be both ? Every Regular Language is a CSL right. 1 votes 1 votes Dhruv Patel commented May 15, 2017 reply Follow Share @Harsh That's correct. Every regular language is CSL. So both are correct. Though regular language answer is more specific. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes R1(R2)* is simply (a+b+c)*....and hence regular joshi_nitish answered May 15, 2017 joshi_nitish comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes L1 is CSL and L2 is regular. then (L2)* will be reguler (by using closure properties) and now L1.(L2)*=CSL.Reguler(push up) CSL.CSL=CSL pawan kumarln answered May 11, 2017 pawan kumarln comment Share Follow See 1 comment See all 1 1 comment reply Gatecoder commented May 12, 2017 reply Follow Share correct i have also same explanation.. 0 votes 0 votes Please log in or register to add a comment.