Computer Science Engineering (CSE)  >  Theory of Computation  >  Test: Turing Machine & Halting Download as PDF

Test: Turing Machine & Halting


Test Description

10 Questions MCQ Test Theory of Computation | Test: Turing Machine & Halting

Test: Turing Machine & Halting for Computer Science Engineering (CSE) 2022 is part of Theory of Computation preparation. The Test: Turing Machine & Halting questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Turing Machine & Halting MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Turing Machine & Halting below.
Solutions of Test: Turing Machine & Halting questions in English are available as part of our Theory of Computation for Computer Science Engineering (CSE) & Test: Turing Machine & Halting solutions in Hindi for Theory of Computation course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Turing Machine & Halting | 10 questions in 10 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Theory of Computation for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Test: Turing Machine & Halting - Question 1

 Which of the following regular expression resembles the given diagram?

Detailed Solution for Test: Turing Machine & Halting - Question 1

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

Test: Turing Machine & Halting - Question 2

 Construct a turing machine which accepts a string with ‘aba’ as its substring.
 

Detailed Solution for Test: Turing Machine & Halting - Question 2

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:

Test: Turing Machine & Halting - Question 3

 The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using finite automata:

Detailed Solution for Test: Turing Machine & Halting - Question 3

The finite automata can be represented as:

Test: Turing Machine & Halting - Question 4

The machine accept the string by entering into hA or it can:

Detailed Solution for Test: Turing Machine & Halting - Question 4

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

Test: Turing Machine & Halting - Question 5

 d(q,X)=(r,Y,D) where D cannot be:

Detailed Solution for Test: Turing Machine & Halting - Question 5

D represents the direction in which automata moves forward as per the queue which surely cannot be a starting variable.

Test: Turing Machine & Halting - Question 6

 Which of the following can accept even palindrome over {a,b}

Detailed Solution for Test: Turing Machine & Halting - Question 6

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

Test: Turing Machine & Halting - Question 7

Which of the functions can a turing machine not perform?

Detailed Solution for Test: Turing Machine & Halting - Question 7

Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.

Test: Turing Machine & Halting - Question 8

If T1 and T2 are two turing machines. The composite can be represented using the expression:

Detailed Solution for Test: Turing Machine & Halting - Question 8

 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.

Test: Turing Machine & Halting - Question 9

 The following turing machine acts like:

Detailed Solution for Test: Turing Machine & Halting - Question 9

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

Test: Turing Machine & Halting - Question 10

What does the following transition graph shows:

Detailed Solution for Test: Turing Machine & Halting - Question 10

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.

18 videos|44 docs|39 tests
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Test: Turing Machine & Halting Page
In this test you can find the Exam questions for Test: Turing Machine & Halting solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Turing Machine & Halting, EduRev gives you an ample number of Online tests for practice