33 votes 33 votes Which of the following three statements are true? Prove your answer. The union of two recursive languages is recursive. The language $\{O^n \mid n\text{ is a prime} \}$ is not regular. Regular languages are closed under infinite union. Theory of Computation gate1992 theory-of-computation normal closure-property proof descriptive + – Kathleen asked Sep 13, 2014 • edited Apr 19, 2021 by Lakshman Bhaiya Kathleen 8.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply Deepak Poonia commented Sep 30, 2021 i edited by Deepak Poonia Jul 16, 2022 reply Follow Share $\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{ , With Proof of each statement:}}$https://youtu.be/QLYJXbQsyaI 15 votes 15 votes Please log in or register to add a comment.
Best answer 36 votes 36 votes True. Recursive languages are closed under union. True. The language is context sensitive (we can write a C code right?) but not context-free (can be proved using pumping lemma for context-free languages). False. Regular languages are closed under finite union but not under infinite union. Rajarshi Sarkar answered Apr 25, 2015 • edited May 19, 2021 by Arjun Rajarshi Sarkar comment Share Follow See all 19 Comments See all 19 19 Comments reply Arjun commented Apr 25, 2015 reply Follow Share Can you prove (or give example) why iii is false? 1 votes 1 votes Rajarshi Sarkar commented Apr 25, 2015 reply Follow Share Yes. Regular languages are closed under finite union, and the proofs runs along the lines that you sketch in the question, however this falls apart under infinite union. We can show this by taking Li={0i1i} for each i (with Σ={0,1}). The infinite union of these languages of course gives the canonical non-regular (context-free) language L={0i1i∣i∈N}.Ref: http://cs.stackexchange.com/a/30459 18 votes 18 votes Rohan Mundhey commented May 9, 2016 reply Follow Share The prime language is 1st CSL language.....so it's also Recursive and also Recurively Enumerable 3 votes 3 votes just_bhavana commented Aug 28, 2017 reply Follow Share ii) is non-regular is true. But can you prove how is it a CSL? 1 votes 1 votes Tuhin Dutta commented Nov 24, 2017 reply Follow Share Does infinite union mean, we need to have infinite no. of states which cannot be true for FA thus false? 0 votes 0 votes air1ankit commented Dec 8, 2017 reply Follow Share (i) The union of two recursive languages is recursive. (ii) The language {On∣n is a prime}{On∣n is a prime} is not regular. how both are true , can you please explain in detail 1 votes 1 votes Sandeep Suri commented Dec 31, 2017 reply Follow Share Regular languages are not closed under infinite union can anyone give proof? @Rajarshi Sarkar 4 votes 4 votes meghna commented Jul 21, 2018 reply Follow Share for regular languages not closed under infinite union ....we can say L1={a1b1}, L2={a2b2}, L3=(a3b3}..... L=L1 U L2 U L3 U...............Ln {infinite union} L={anbn|n>=1}...........................not regular. 23 votes 23 votes minal commented Sep 8, 2018 reply Follow Share http://www.idt.mdh.se/kurser/dva337/compendia/turing_machines.pdf prove for 1st option 0 votes 0 votes Golam Murtuza commented May 19, 2019 reply Follow Share above link is not working 0 votes 0 votes Satbir commented Jul 23, 2019 reply Follow Share This is not complete answer since proofs of the 3 statements are not given in the answer. 2 votes 2 votes Golam Murtuza commented Aug 16, 2019 i edited by Golam Murtuza Aug 17, 2019 reply Follow Share @Satbir Example is given in comment for option 3. 1 votes 1 votes Satbir commented Aug 17, 2019 reply Follow Share I am talking about all the three options. 1 votes 1 votes Golam Murtuza commented Aug 17, 2019 reply Follow Share Recursive languages are closed under union operation as you can create a new TM ( combinely from the two TMs lets sayTM1, TM2) which can say "YES" or "NO" for all possible option .So new TM is also Recursive. For option 2 you can check this link https://math.stackexchange.com/questions/1550522/how-to-prove-that-l-ap-p-is-prime-isnt-regular 1 votes 1 votes Manu Shaurya commented May 19, 2021 reply Follow Share Can someone explain option 2, I understood it can be a recursive language, but how can be it done using a Finite sized tape (Linear bounded Automaton)? 0 votes 0 votes svas7246 commented Aug 12, 2021 reply Follow Share @meghna Perfect answer quick and concise 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share @meghna how can u take Ln in union as it is not regular here we have to show that if all the infinite languages are regular then there union is not regular. 0 votes 0 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share @Pranavpurkar Finite is always regular. All of L1={a1b1}, L2={a2b2}, L3=(a3b3}... are finite languages, hence are regular. @meghna ‘s example is correct. Link 1 votes 1 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00ohh i think i got my mistake.the mistake i did was , as she considered L1 = $a^{1}b^{1}$ so i got confused with Ln (it would be better if some other variable was taken)as then Ln = $a^{n}b^{n}$ but here n is some constant , that’s why finite.Thanks buddy! 1 votes 1 votes Please log in or register to add a comment.