1
GATE CSE 2001
MCQ (Single Correct Answer)
+2
-0.6
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,} $$ does the computation of $$M$$ on $$w$$ visit the state $$q''$$

Which of the following statements about $$X$$ is correct?

A
$$X$$ is decidable
B
$$X$$ is undecidable but partially decidable
C
$$X$$ is undecidable and not even partially decidable
D
$$X$$ is not a decision problem
2
GATE CSE 1991
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$
A
It could be un-decidable
B
It is Turing-machine recognizable
C
It is a regular language
D
It is a context-sensitive language
3
GATE CSE 1990
MCQ (More than One Correct Answer)
+2
-0.6
It is decidable whether:
A
An arbitrary Turing machine halts after 10 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the product of two numbers.
D
None of the above.
4
GATE CSE 1989
MCQ (More than One Correct Answer)
+2
-0.6
Which of the following problems are un-decidable?
A
Membership problem in context - free languages.
B
Whether a given context - free language is regular.
C
Whether a finite state automation halts on all inputs.
D
Membership problem for type $$0$$ languages.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12