+19 votes
991 views

Which of the following three statements are true? Prove your answer.

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.
asked
edited | 991 views

## 1 Answer

+17 votes
Best answer
1. True. Recursive languages are closed under union.
2. True. The language is Turing Machine acceptable.
3. False. Regular languages are closed under finite union.
answered by Boss (33.8k points)
edited by
+1
Can you prove (or give example) why iii is false?
+8

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

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

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.

0
0
above link is not working
0
This is not complete answer since proofs of the 3 statements are not given in the answer.

+15 votes
2 answers
1
+2 votes
1 answer
2
0 votes
0 answers
3
+29 votes
4 answers
4
+14 votes
2 answers
5
+12 votes
2 answers
6
0 votes
1 answer
7