retagged by
419 views
1 votes
1 votes

Find True $\left ( T \right )$ or False $\left ( F \right )$of the following statements :

  1. If $A$ is recursive then complement of $A$ is also recursive
  2. If $A$ and $B$ are recursive sets then $A$ intersection $B$ is not always is recursive set.
  3. Every recursive set is recursive enumerable and vice-versa
  1.      $TTT$ 
  2.      $TFT$   
  3.      $TFF$ 
  4.      $FFT$
retagged by

3 Answers

Best answer
2 votes
2 votes

(i) If A is recursive then complement of A is also recursive

Recursive languages are closed under intersection. So, this is TRUE.

(ii) If A and B are recursive sets then A intersection B is not always is recursive set.

Recursive languages (or sets) are closed under intersection. So the intersection of two recursive languages will always be a recursive language. So, this is FALSE.

(iii) Every recursive set is recursive enumerable and vice-versa

Recursive set is a proper subset of recursively enumerable set. So, every recursive set is also recursively enumerable. But reverse is not true, i.e. there are sets which are recursively enumerable but not recursive. Proof of this can be found in any standard TOC textbook(like Peter Linz). So, this statement is FALSE.

Option (C) - TFF 

selected by
0 votes
0 votes

What is the diffrence between recursive set and recursive language and how  there intersection is not recursive set?plzz explain!!

Tho i got dis from wiki but dint  understand-- If A and B are recursive sets then A ∩ BA ∪ B and the image of A × B under the Cantor pairing function are recursive sets!!

0 votes
0 votes
According to Chomsky hierachy
1. TRUE ===> Recursive comes under complement .
2 FALSE ==> Recursive comes under intersection
3. FALSE ==> REC subset RE but not vise-versa
Answer:

Related questions