in Theory of Computation edited by
3,469 views
26 votes

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.
in Theory of Computation edited by
3.5k views

1 Answer

29 votes
 
Best answer
  1. True. Recursive languages are closed under union.
  2. True. The language is context sensitive (we can write a C code right?) but not context-free (can be proved using pumping lemma for context-free languages).
  3. False. Regular languages are closed under finite union but not under infinite union. 
edited by

16 Comments

Can you prove (or give example) why iii is false?
1

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

16
The prime language is 1st CSL language.....so it's also Recursive and also Recurively Enumerable
3
ii) is non-regular is true. But can you prove how is it a CSL?
1
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
1
Regular languages are not closed under infinite union can anyone give proof? @Rajarshi Sarkar
4

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.

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

@Satbir

Example is given  in comment for option 3.

1
I am talking about all the three options.
1

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

1
Can someone explain option 2, I understood it can be a recursive language, but how can be it done using a Finite sized tape (Linear bounded Automaton)?
0
@meghna  Perfect answer quick and concise
0

Related questions