Time Left - 15:00 mins

GATE 2022: Theory Of Computation Quiz-7

Attempt now to get your rank among 292 students!

Question 1

Which among the following is the only difference between Turing Machine and Finite Automaton ?

Question 2

Which one type of Turing machine is more powerful than others?

Question 3

Match the languages to their corresponding time taken to accept the string :

Question 4

Consider the following statements:
1) A turing machine is more powerful than finite state machine because it has no finite state
2) A finite state machine can be assumed to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
Which one of the above statements holds true?

Question 5

Minimum number of stacks required by PDA to behave like TM?

Question 6

Consider the following transition table of a Turing machine and statements regarding it.

Statement 1- the Given Turing machine is a non-halting Turing machine.

Statement 2- the Given Turing machine is halting Turing machine.

Statement 3- Language accepted by the above Turing machine is a type of languages that is closed under intersection operation.

Number of statements that are correct is ____.

  • 292 attempts
  • 0 upvotes
  • 1 comment
Oct 13GATE & PSU CS