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.6k 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 Show 16 previous comments 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.