The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

Which of the following statements is/are **FALSE**?

- For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
- Turing recognizable languages are closed under union and complementation.
- Turing decidable languages are closed under intersection and complementation.
- Turing recognizable languages are closed under union and intersection.

- 1 and 4 only
- 1 and 3 only
- 2 only
- 3 only

Recursive Enumerable for TM is possible

if L belongs to RE, then we apply any string to TM -> either it says YES or(NO or INFINITE LOOP)

But for L(complement) { Language out side the RE and within the SET of all LANGUAGES)

TM is not possible for such language , therefore RE is not come under COMPLEMENT

Similar for SET DIFFERENCE,

please correct me !

+27 votes

Best answer

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.

+6 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/**

+2 votes

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

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

Option 3- 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

Option 4 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 **

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users