0 votes 0 votes union of all finite subsets of regular language is regular. at least one proper infinite subset(if exists) of infinite CFL is regular. which is true?? abhishek tiwary asked Nov 29, 2017 abhishek tiwary 900 views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply Ashwin Kulkarni commented Nov 29, 2017 reply Follow Share 1st is true i guess. (because infinite union of RL is not possible) 0 votes 0 votes Shubhanshu commented Nov 29, 2017 reply Follow Share 1st one is not regular. Consider a regular language L over a and b. Now no of all finite subset of L is infinite and union them all is nothing but infinite union of regular language which is not regular. 2nd one is also not regular. Consider a language L over a and b where no of a is equal to number of b. And its proper infinite subset of L is L1 is {anbn} which is clearly not regular. Hence non of them is true. 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share @shubhanshu proper subset does not include the set itself 0 votes 0 votes Shubhanshu commented Nov 29, 2017 reply Follow Share Which one is you taking about? 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share No you're correct, I mistook it 0 votes 0 votes abhishek tiwary commented Nov 29, 2017 reply Follow Share @ Shubhanshu for second s there no any other possiblity?? 0 votes 0 votes Shubhanshu commented Nov 29, 2017 reply Follow Share You can take other example also but that should be counter case to prove the above statement as false. 0 votes 0 votes abhishek tiwary commented Nov 29, 2017 reply Follow Share @ Shubhanshu, just_bhavana take CFL=x*(a^nb^n)n>=0 so at least infinite proper subset of CFL=x* which is regular??? 0 votes 0 votes just_bhavana commented Nov 30, 2017 reply Follow Share @abhishek but there is a case when infinite proper subset turns out to be not regular. Even if once we get a counter example, then the statement is false. For language $L = \left \{ a^{n}b^{m}|n,m\geq 0, n\geq m\right \}$ and its infinite proper subset $L^{s} = \left \{ a^{n}b^{n}|n\geq 0\right \}$ which is CFL 0 votes 0 votes joshi_nitish commented Nov 30, 2017 reply Follow Share @shubhanshu statement 1) will be true, let L ={a, ab, abb, aabb, abaa......} // let it be some regular language now one group 'G' of its finite subsets will be {a} , {ab}, {abb}, {aabb}, {abaa}...... // sets of cardinaltiy=1 now if you just take union of group 'G' subsets, you will get L back. Now union of any other subset is irrelevant, because it is already absorbed in L. this simply means that $\bigcup_{i=1}^{n}$Li = L , where Li is finite subset of L... so finally more generally we can say that union of all finite subsets of language L is again language L . 4 votes 4 votes Shubhanshu commented Nov 30, 2017 reply Follow Share So you mean to say. DFA of union of all subsets of that language is nothing but DFA of L only. 0 votes 0 votes joshi_nitish commented Nov 30, 2017 reply Follow Share yes, exactly, because DFA of union of all subsets of that language L is nothing but itself L. 0 votes 0 votes Ashwin Kulkarni commented Dec 1, 2017 reply Follow Share Yes That's what I said earlier it is not infinite union it is finite union. Just I was unable to put into the words. Thanks for the explanation @joshi_nitish. 0 votes 0 votes Hemant Parihar commented Dec 1, 2017 reply Follow Share For 2nd, if my CFL is {$a^n$$b^n$ | n>= 1} Then which infinite proper subset of it will be regular? 0 votes 0 votes joshi_nitish commented Dec 1, 2017 reply Follow Share yes, the 2nd statement is false 1 votes 1 votes Hemant Parihar commented Dec 2, 2017 reply Follow Share @joshi_nitish, What will be the answer if we have "Union of all infinite subsets of regular language"? 0 votes 0 votes joshi_nitish commented Dec 2, 2017 reply Follow Share @Hemant "Union of all infinite subsets of regular language" due to word all, every possible string of L will be present in newly created set ($\bigcup_{i=1}^{n}$Li) and also no outsider string(which is not present in L) will be present in newly created set ($\bigcup_{i=1}^{n}$Li) therefore finally union of all infinite subsets of regular language L is nothing but L 1 votes 1 votes Please log in or register to add a comment.