This set of Automata Theory Questions and Answers for Freshers focuses on ” The Language of Turing Machine-2″.

1. The class of recursively ennumerable language is known as:

a) Turing Class

b) Recursive Languages

c) Universal Languages

d) RE

View Answer

Explanation: RE or recursively ennumerable is only called the class of recursively ennumerable language.

2. A language L is said to be Turing decidable if:

a) recursive

b) TM recognizes L

c) TM accepts L

d) None of the mentioned

View Answer

Explanation: A language L is recursively ennumerable if there is a turing machine that accepts L, and recursive if there is a TM that recognizes L.(Sometimes these languages are alse called Turing-acceptable and Turing-decidable respectively).

3. Which of the following statements are false?

a) Every recursive language is recursively ennumerable

b) Recursively ennumerable language may not be recursive

c) Recursive languages may not be recursively ennumerable

d) None of the mentioned

View Answer

Explanation: Every recursive language is recursively ennumerable but there exists recursively ennumerable languages that are not recursive. If L is accepted by a Non deterministic TM T, and every possible sequence of moves of T causes it to halt, then L is recursive.

4. Choose the correct option:

Statement: If L1 and L2 are recursively ennumerable languages over S, then the following is/are recursively ennumerable.

a) L1 U L2

b) L2 ∩ L2

c) Both (a) and (b)

d) None of the mentioned

View Answer

Explanation: Both the union and intersection operations preserve the property of recursive ennumerablity(Theorem).

5. If L is a recursive language, L’ is:

a) Recursive

b) Recursively Ennumerable

c) Both (a) and (b)

d) None of the mentioned

View Answer

Explanation: If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the two outputs. And every recursive language is recursively ennumerable.

6. Choose the appropriate option:

Statement: If a language L is recursive, it is closed under the following operations:

a) Union

b) Intersection

c) Complement

d) All of the mentioned

View Answer

Explanation: The closure property of recursive languages include union, intersection and complement operations.

7. A recursively ennumerable language L can be recursive if:

a) L’ is recursively ennumerable

b) Every possible sequence of moves of T, the TM which accept L, causes it to halt

c) Both (a) and (b)

d) None of the mentioned

View Answer

Explanation: Theorem- If L is a recursively ennumerable language whose complement is recursively ennumerable, then L is recursive.

8. A language L is recursively ennumerable if L=L(M) for some turing machine M.

Which among the following cannot be among A, B and C?

a) yes w ∈ L

b) no w ∉ L

c) M does not halt w ∉ L

d) None of the mentioned

View Answer

9. State true or false:

Statement: An ennumerator is a turing machine mwith extra output tape T, where symbols, once written, are never changed.

a) true

b) false

View Answer

Explanation: To ennumerate a set means to list the elements once at a time, and to say that a set is ennumerable should perhaps mean that there exists an algorithm for ennumerating it.

10. A Language L may not be accepted by a Turing Machine if:

a) It it is recursively ennumerable

b) It is recursive

c) L can be ennumerated by some turing machine

d) None of the mentioned

View Answer

Explanation: A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory for Freshers, __here is complete set of 1000+ Multiple Choice Questions and Answers__.