Automata Theory Questions and Answers for Freshers on ” The Language of Turing Machine″.
1. The class of recursively ennumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE
Answer: d
Clarification: 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
Answer: a,b
Clarification: 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
Answer: c
Clarification: 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
Answer: c
Clarification: 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
Answer: c
Clarification: Theorem- If L is a recursively ennumerable language whose complement is recursively ennumerable, then L is recursive.
8. 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
Answer: a
Clarification: 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.
9. 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
Answer: b
Clarification: 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.