Test by Bikram | Mock GATE | Test 1 | Question: 28

Question

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

• A.      $TTT$ 
• B.      $TFT$   
• C.      $TFF$ 
• D.      $FFT$

Comments

please clarify about recursive sets and languages, how to think of sets??

---

@redbloodpro

read these slides, it will clear

http://krchowdhary.com/toc/18-r-re-langs.pdf

Answer 1

(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 

Answer 2

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 ∩ B, A ∪ B and the image of A × B under the Cantor pairing function are recursive sets!!

Comments

@swap_It

Read

1. http://krchowdhary.com/toc/18-r-re-langs.pdf
2. http://cs.stackexchange.com/questions/7585/recursive-and-recursively-enumerable-language-definition-for-a-layman
3. http://stackoverflow.com/questions/33467040/what-is-the-difference-between-recursive-and-recursively-enumerable-languages

---

The intersection R and RE languages is RE.

Proof.

Let L1 and L2 be languages recognized by Turing machines M1 and M2, respectively.

Let a new TM M3 is for the intersection L1 ∩L2.

M3 simply executes M1 and M2 one after the other on the same input w: It first simulates M1 on w. If M1 halts by accepting it, M3 clears the tape, copies the input word w on the tape and starts simulating M2.

If M2 also accepts w then M3 accepts. Clearly, M3 recognizes L1 ∩ L2, and if M1 and M2 halt on all inputs then also M3 halts on all inputs.

Answer 3

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