760 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.
edited | 760 views

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.
edited by
+1
Can you prove (or give example) why iii is false?
+5

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

0
The prime language is 1st CSL language.....so it's also Recursive and also Recurively Enumerable
0
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

1.DETERMISTIC CONTEXT FREE LANGUAGE

2.CONTEXT SENSITIVE  LANGUAGE

3.RECURSIVE LANGUAGE

4.RECURSIVE ENUMERABLE LANGUAGE

ALL ABOVE ARE BOUND UNDER WHICH OPERATIONS.?
+1
@arjun sir can you please tell me difference b/w finite union and infinite union ??
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
+2
Regular languages are not closed under infinite union can anyone give proof? @Rajarshi Sarkar
+2

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

1
2