This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Language of Turing Machine-2”.
1. The class of recursively enumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE
View Answer
Explanation: RE or recursively enumerable is only called the class of recursively enumerable language.
2. A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) recursive & TM recognizes L
View Answer
Explanation: A language L is recursively enumerable 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 enumerable
b) Recursively enumerable language may not be recursive
c) Recursive languages may not be recursively enumerable
d) None of the mentioned
View Answer
Explanation: Every recursive language is recursively enumerable but there exists recursively enumerable 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 enumerable languages over S, then the following is/are recursively enumerable.
a) L1 U L2
b) L2 ∩ L2
c) Both L1 U L2 and L2 ∩ L2
d) None of the mentioned
View Answer
Explanation: Both the union and intersection operations preserve the property of recursive enumerablity(Theorem).
5. If L is a recursive language, L’ is:
a) Recursive
b) Recursively Enumerable
c) Recursive and Recursively Enumerable
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 enumerable.
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 enumerable language L can be recursive if:
a) L’ is recursively enumerable
b) Every possible sequence of moves of T, the TM which accept L, causes it to halt
c) L’ is recursively enumerable and every possible sequence of moves of T, the TM which accept L, causes it to halt
d) None of the mentioned
View Answer
Explanation: Theorem- If L is a recursively enumerable language whose complement is recursively enumerable, then L is recursive.
8. A language L is recursively enumerable 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 enumerator is a turing machine with extra output tape T, where symbols, once written, are never changed.
a) true
b) false
View Answer
Explanation: To enumerate a set means to list the elements once at a time, and to say that a set is enumerable should perhaps mean that there exists an algorithm for enumerating it.
10. A Language L may not be accepted by a Turing Machine if:
a) It is recursively enumerable
b) It is recursive
c) L can be enumerated by some turing machine
d) None of the mentioned
View Answer
Explanation: A language L is recursively enumerable if and only if it can be enumerated by some turing machine. A recursive enumerable language may or may not be recursive.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Automata Theory Books