edited by
20,874 views
40 votes
40 votes

Which of the following statements is/are FALSE?

  1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
  2. Turing recognizable languages are closed under union and complementation.
  3. Turing decidable languages are closed under intersection and complementation.
  4. Turing recognizable languages are closed under union and intersection.
  1. $1$ and $4$ only    
  2. $1$ and $3$ only    
  3. $2$ only    
  4. $3$ only
edited by

6 Answers

Best answer
57 votes
57 votes

Recursive enumerable languages are not closed under complement . while recursive languages are.

Both Recursive and Recursive enumerable languages are closed under intersection, union, and kleene star.

http://gatecse.in/wiki/Closure_Property_of_Language_Families

Non-Deterministic TM is equivalent to DTM

Only $2$ is false. Option C is correct.

Note: Turing decidable language mean Recursive language and Turing recognizable language mean recursive enumerable language.

edited by
13 votes
13 votes

Answer is (C) Part.

For every point i am mentioning some small intuition or some hint as per my knowledge which may help readers -->

For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

If something is computable then there exists a DTM(Deterministic Turing Machine) for it. 

Turing recognizable languages are closed under union and complementation.

Turing recognizable languages are known as RE languages whose complement may not be RE. But RE languages are closed under Intersection and Union.

Turing decidable languages are closed under intersection and complementation

Turing decidable languages means REC( or recursive languages). We have HTM(Halting Turing Machine) corresponding to REC.

For proof please refer --> http://www.eecs.wsu.edu/~cook/tcs/l19.html

Just for recalling a quick table is mentioned on --> https://gatecse.in/closure-property-of-language-families/

edited by
6 votes
6 votes

$\text{Option A}:$  A nondeterministic Turing machine is a generalization of the standard TM for which every configuration may yield none, or one or more than one next configurations. reference : -http://www.cs.rpi.edu/~goldberg/14-CC/02-ndt.pdf

$\text{Option B}:$   Turing recognizable language ( Recursive Enumerable language ) is not closed under complementation because as given in figure we can see if we complement it then we don't know about loop  but closed under union 

$\text{Option C}:$ Turing Decidable language means Recursive language so it is closed under Complementation why we can see in figure

 

as well as if is closed under intersection as given figure 

$\text{Option D}:$ is also true because we can find intersection of two RE language as well union as previous figure 

*There is little modification in figure 1 which is there is loop in outer block 

Hence option 2 is FALSE

edited by
1 votes
1 votes
1) True, for every Non deterministic Turing machine, there exist an equivalent deterministic Turing machine

2) False,  Turing Recognizable languages i.e Recursive enumerable languages are closed under union but not under complementation.

3) True, Turing decidable language i.e Recursive languages are closed under intersection as well as complementation.

4) True, Turing Recognizable languages i.e Recursive enumerable languages are closed under union and intersection.

So, only 2 is false, option c is correct.
Answer:

Related questions

44 votes
44 votes
2 answers
1