NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
1

GATE CSE 2001

MCQ (Single Correct Answer)
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)
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)
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.

Explanation



Case (a):
Just run the TM for 10 steps and see it halts or not. So this is decideable.

Case (b):
The printing problem of TMs is Undecidable. This can be reduce to the halting problem when the TM halts let it print something.

Case (c):
Multiplication, Addition can be done by TM so this is decidable.
4

GATE CSE 1989

MCQ (More than One Correct Answer)
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.
Write for Us

Do you want to write for us? Help us by contributing to our platform.

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12