3,469 views

1. The union of two recursive languages is recursive.
2. The language $\{O^n \mid n\text{ is a prime} \}$ is not regular.
3. Regular languages are closed under infinite union.

1. True. Recursive languages are closed under union.
2. 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).
3. False. Regular languages are closed under finite union but not under infinite union.

Can you prove (or give example) why iii is false?

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}.

The prime language is 1st CSL language.....so it's also Recursive and also Recurively Enumerable
ii) is non-regular is true. But can you prove how is it a CSL?
Does infinite union mean, we need to have infinite no. of states which cannot be true for FA thus false?
(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
Regular languages are not closed under infinite union can anyone give proof? @Rajarshi Sarkar

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.

This is not complete answer since proofs of the 3 statements are not given in the answer.
edited

@Satbir

Example is given  in comment for option 3.

I am talking about all the three options.

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

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)?
@meghna  Perfect answer quick and concise