Automata Theory Questions and Answers -Turing Machine and Halting

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Turing Machine and Halting”.

1. Which of the following regular expression resembles the given diagram?
The given diagram is a transition graph for a turing machine
a) {a}*{b}*{a,b}
b) {a,b}*{aba}
c) {a,b}*{bab}
d) {a,b}*{a}*{b}*
View Answer

Answer: b
Explanation: The given diagram is a transition graph for a turing machine which accepts the language with the regular expression {a,b}*{aba}.

2. Construct a turing machine which accepts a string with ‘aba’ as its substring.
a)The turing machine which accepts a string with ‘aba’ as its substring - option a
b)The turing machine which accepts a string with ‘aba’ as its substring - option b
c)The turing machine which accepts a string with ‘aba’ as its substring - option c
d)The turing machine which accepts a string with ‘aba’ as its substring - option d
View Answer

Answer: c
Explanation: The language consist of strings with a substring ‘aba’ as fixed at its end and the left part can be anything including epsilon. Thus the turing machine uses five states to express the language excluding the rejection halting state which if allowed can modify the graph as:
The turing machine uses 5 states to express language excluding rejection halting state

3. The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using finite automata:
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: a
Explanation: The finite automata can be represented as:
The finite automata of number of states required to automate the last question
advertisement
advertisement

4. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) explicitly reject x by entering into hR and enter into an infinte loop
d) None of the mentioned
View Answer

Answer: c
Explanation: Three things can occur when a string is tested over a turing machine:
a) enter into accept halting state
b) enter into reject halting state
c) goes into loop forever

5. d(q,X)=(r,Y,D) where D cannot be:
D is direction in which automata moves forward as per the queue
a) L
b) R
c) S
d) None of the mentioned
View Answer

Answer: c
Explanation: D represents the direction in which automata moves forward as per the queue which surely cannot be a starting variable.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
View Answer

Answer: c
Explanation: A language generating strings which are palindrome is not regular, thus cannot b represented using a finite automaton.

7. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
View Answer

Answer: d
Explanation: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
advertisement

8. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
View Answer

Answer: a
Explanation: If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.

9. The following turing machine acts like:
The turing machine acts like Delete a symbol
a) Copies a string
b) Delete a symbol
c) Insert a symbol
d) None of the mentioned
View Answer

Answer: b
Explanation: A turing machine does the deletion by changing the tape contents from yaz to yz, where y belongs to (S U {#})*.
advertisement

10. What does the following transition graph shows:
The composite TM accepts the language of palindromes over {a, b}
a) Copies a symbol
b) Reverses a string
c) Accepts a pal
d) None of the mentioned
View Answer

Answer: c
Explanation: The composite TM accepts the language of palindromes over {a, b} by comparing the input string to its reverse and accepting if and only if the two are equal.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.