Turning Machine Questions

MCQ bookmark_border

1.

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

Correct Answer: D

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

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

Correct Answer: A

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

The following turing machine acts like:

 

A

Copies a string

B

Delete a symbol

C

Insert a symbol

D

None of the mentioned

Correct Answer: B

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

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

Correct Answer: D

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

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

A

T1T2

B

T1 U T2

C

T1 U T2

D

None of the mentioned

Correct Answer: A

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

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

Correct Answer: C

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

Construct a turing machine which accepts a string with

A

B

C

D

Correct Answer: C

The language consist of strings with a substring

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

Turing machine was invented by:

A

Alan Turing

B

Turing man

C

Turing taring

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

In one move the turing machine:

A

May change its state

B

Write a symbol on the cell being scanned.

C

Move the head one position left or right

D

All of the above

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Turing machine can be represented using:

A

Transition table

B

Transition diagram

C

Instantaneous description

D

All of these

Correct Answer: D

Check Answer report_problem Report forum Discussion