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.

## 1 Answer

### 16 Comments

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 L_{i}={0^{i}1^{i}} for each i (with Σ={0,1}). The infinite union of these languages of course gives the canonical non-regular (context-free) language L={0^{i}1^{i}∣i∈N}.

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