The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
912 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 in Theory of Computation by Veteran (59.9k points)
edited by | 912 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 (34.1k points)
edited by
+1
Can you prove (or give example) why iii is false?
+7

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


Ref: http://cs.stackexchange.com/a/30459

+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
+6

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,910 questions
52,287 answers
182,227 comments
67,728 users