TIFR CSE 2014 | Part B | Question: 14

Question

Which the following is FALSE?

• A. Complement of a recursive language is recursive.
• B. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine.
• C. Complement of a context free language can be recognized by a Turing machine.
• D. If a language and its complement are both recursively enumerable then it is recursive.
• E. Complement of a non-recursive language can never be recognized by any Turing machine.

Comments

Why is D incorrect my reasoning is that recursively enumerable languages do not have a complement.So what is the complement of a recursively enumerable language?

Isn't Recursively Enumerable superset of Recursive so how does its complement become recursive.

Please correct my reasoning,so that this misconception is eliminated.

---

@sripo

U can use the fact that recursive languages are closed under the compliment and every recursive language is recursively enumerable.

If u r saying that if a language and its complement is recursively enumerable, then it means u want to say that Even recursively enumerable languages are closed under complement and if this is true then there will be no difference between recursively enumerable and recursive languages, I mean the same set can represent both languages and  So language will become recursive..

---

$A:true$

$B:true$

$C:true$

$D:true$

$E:false$

Image for D

---

Note: A language is Recursively enumerable (RE) but not recursive (REC) then it complement is non-RE.

---

option E is false.

Answer 1

• A. True. For a recursive language, we have a TM which says for any string "w", "yes" if it belongs to the language and "no" if it does not. For the complement of a recursive language we just have to reverse 'yes' and 'no' conditions and this is possible with a slight modification to the original TM. So, the new language is also recursive.
• B. True. Non-determinism does not add any recognizing power to a Turing machine though it can affect the time complexity in solving a problem.
• C. True. Complement of CFL is recursive. and recursive language is recognized by Turing machine. So, complement of a context free language can be recognized by TM
• D. True. If a language is r.e., we have a TM which says "yes" whenever a given string belongs to L. Similarly, if its complement is r.e., we have a TM which says "yes", whenever a string does not belong to the language. So, combining both we can always say "yes" if a string belongs to the language and "no" if a string does not belong to L $\implies$ L is recursive.
• E. False.
  Non-recursive Language can be:- (a) r.e. or (b) Non r.e.
  As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM). But, if the language is not r.e. its complement may be r.e. (which Can be recognized by TM).  option E is false.
  Example:- 
  $L=\{\langle M,w\rangle \mid M \text{ is a TM and it does not halt on string } w\}.$ //Non RE (complement of halting problem)
  $L^c=\{\langle M,w \rangle \mid M \text{ is a TM and it halts on string } w\}$ //RE but not Recursive //recognized by TM (halting problem)

So, answer is (E).

Comments

E option says about "complement"

---

ok sir, edited .plz check :)

---

No. Non r.e. languages cannot be recognized by a TM- because then it becomes r.e. as per definition. Complement of a r.e. language may or may not be r.e. (r.e. set not closed under complement). The may case is making option E false here.

---

Sir, they say complement of a nonrecursive language. if the complement of the RE language  is RE then the language is both RE and recursive. but it is possible that the nonrecursive  language is non RE ,but its complement is RE , hence E is false

---

@srestha ur this statement is not true.

"we know non recursive enumerable language can be recognized by Turing Machine"

Actually TM can accept upto REL it never accepts NREL.

If u agree U can Edit Option E as Below :-

Non-recursive Language means:- a) REL or b) NREL

Now  REL is not closed under complement so Now Complement of REL is either

1.REL(Indeed RS)// Can be accepted by TM...so option E is false.

or

2.NREL. //Cant be accepted by TM

---

yes, u r correct

---

Added :)

---

Thanks :) @srestha

---

@Sreshta and Rajesh
Plz always use standard terminology.
ye REL, NREL and RS..kya h ye sab ? :P

---

REL:-Recursive Enumerable Language

NREL:-Non- Recursive Enumerable Language

RS:- Recursive Set

Plz list the standard terminologies..Many a time i too confuse..with Shortcuts :P

---

ohh, Then your argument about E is Incorrect.

See my reasoning, If it is valid or not, comment about it :)

In option E, they are talking about a language which is NOT recursive, Then of course 2 cases-
(L is a language which is Not REC)
1. L is RE
2. L is Not even RE

1. If L is RE, then its complement MUST be $\text{Not RE}$.
Bcoz if L complement is RE (then it hs to be REC) that makes L REC, Which is contradiction..
(What you are doing is, You are saying that L is RE, so its complement may be REC therefore It is Turing recognisable -— This reasoning is wrong, bcoz it contradicts given statement itself.  )

Correct Reasoning must be- From Case 1 we can not conclude that E is False.

Case2: If L is Not RE, then its complement may be REC (or Not RE also). Therefore I can say E is false.

---

@Sachin Completely Agree with U. I will Edit the ans soon..but before that 

I need a reference for ur STRONG claim...atleast one example for

if L is not RE, then its complement may be REC.(I agree with Not RE part)

WRT to ur quotation...

Case2: If L is Not RE, then its complement may be REC (or Not RE also).

---

Opps !
By mistake i wrote REC there, I meant to write "RE" there. Sorry about that :(
Case 2 is:  If L is Not RE, then its complement may be RE (or Not RE also).

---

Thanks for pointing out my mistake..and see the edited Ans.

---

@sachin ..A request ..don't edit the comments in between...Else those who will read the comments in future  will find themselves in ambiguous state.

---

Yes u r right, I unedited the comments, but it will still show "Edited" :(

Thnks for consideration and editing answer. :)

---

@Sachin,

According to Turing Thesis, which says any problem can be solved using TM. In this sense, can we say option E is false?

Please correct me if i am wrong?

---

B)True. Non-determinism does not add any recognizing power to a Turing machine though it can affect the time complexity in solving a problem.

 

 

explain please

---

Deterministic means There is only one transition fr a input ....

No deterministic means there r many transition fr a input .... . So choosing between them increases time complexity ....

---

According to me option C is also incorrect as turing machine cannot read epsilon.
So complement of a CFL may contain epsilon which cannot be read by TM.

---

@Srivathsa   I guess your assumption is wrong; the Turing machine does read epsilon.

https://gateoverflow.in/83694/turing-machine

---

Thank u very much @Aadesh i did not know that

---

As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM).

 

If language is RE its complement MAY OR MAY NOT be RE should be the correct statement, right?

Answer 2

According to me
Option C and Option E both are false.
As TM cannot recognise epsilon, complement of a CFL can have epsilon.