The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
603 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.4k points)
edited by | 603 views

1 Answer

+16 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?
+4

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

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
please any one tell me

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


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

34,770 questions
41,731 answers
118,876 comments
41,381 users