Automata Theory Questions and Answers – The Language of Turing Machine-2

«
»

This set of Automata Theory Questions and Answers for Freshers 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

Answer: d
Explanation: RE or recursively enumerable is only called the class of recursively enumerable language.
advertisement

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

Answer: d
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

Answer: c
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.
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

Answer: c
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

Answer: c
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.
advertisement

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

Answer: d
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

Answer: c
Explanation: Theorem- If L is a recursively enumerable language whose complement is recursively enumerable, then L is recursive.
advertisement

8. A language L is recursively enumerable if L=L(M) for some turing machine M.
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

Answer: d
Explanation:
For turing machine M language L is recursively enumerable if L is L(M)

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

Answer: a
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.
advertisement

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

Answer: b
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 for Freshers, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.