Which of the following statements are undecidable?For a given Turing Machine M,

does M halt on an empty input tape

does M halt for anly inputs at all?

is L(M) regular? Context free? Turing decidable?

Which of the following is incorrect according to rice theorem?Let S be a set of language hat is non trivial:

there exists a TM that recognizes the language in S

there exists a TM that recognizes the language not in S

it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S

Explore topic-wise MCQs in Automata Theory.

This section includes 6 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.

1.	Can a Modified PCP problem be reduced to PCP?
A.	yes
B.	no
Answer» B. no

Discussion

2.	State true or false: Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.
A.	true
B.	false
Answer» B. false

Discussion

3.	Which of the following statements are undecidable? For a given Turing Machine M,
A.	does M halt on an empty input tape
B.	does M halt for anly inputs at all?
C.	is L(M) regular? Context free? Turing decidable?
D.	all of the mentioned
Answer» E.

Discussion

4.	Which of the following is incorrect according to rice theorem? Let S be a set of language hat is non trivial:
A.	there exists a TM that recognizes the language in S
B.	there exists a TM that recognizes the language not in S
C.	it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S
D.	all of the mentioned
Answer» E.

Discussion

5.	Fill in the blank with reference to Rice s theorem. For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
A.	partial functions
B.	piecewise functions
C.	all of the mentioned
D.	none of the mentioned
Answer» B. piecewise functions

Discussion

6.	According to the rice s theorem, If P is a non trivial property, Lp is :
A.	infinite
B.	decidable
C.	undecidable
D.	none of the mentioned
Answer» D. none of the mentioned

Discussion

Explore topic-wise MCQs in Automata Theory.

Can a Modified PCP problem be reduced to PCP?

State true or false:Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

Which of the following statements are undecidable?For a given Turing Machine M,

Which of the following is incorrect according to rice theorem?Let S be a set of language hat is non trivial:

Fill in the blank with reference to Rice s theorem.For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.

According to the rice s theorem, If P is a non trivial property, Lp is :

State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

Which of the following statements are undecidable?
For a given Turing Machine M,

Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:

Fill in the blank with reference to Rice s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.