2.5k views

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 | 2.5k views
0

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,

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
0
+1
0

just by heart https://gatecse.in/closure-property-of-language-families/ this table and enjoy....u will feel free bro

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

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

edited
+1 vote
(C) 2 only

1
2
3
4
5
6