Computer Science and Information Technology
GATE CSE concept:turing-machines PYQs
Build your understanding with focused practice from past exam papers.
How to practice concept:turing-machines
Attempt a question, record the concept and assumptions, then check the available answer. Rework mistakes after revising the relevant concepts. Topic tags can overlap; review the question context.
Questions 1–7 of 7. Imported answers require independent review unless marked reviewed.
Question 13
Open questionCS2MCQ1 markNeeds review
Which one of the following statements is equivalent to the following assertion?
Turing machine
decides the language
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 46
Open questionCSMSQ2 marksNeeds review
Which of the following is/are undecidable?
Your answerSelect all correct options. You can choose more than one.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 39
Open questionCSMCQ2 marksNeeds review
For a Turing machine
,
denotes an encoding of
. Consider the following two languages.
Which one of the following options is correct?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 26
Open questionCSMCQ2 marksNeeds review
Which of the following languages are undecidable? Note that
indicates encoding of the Turing machine
.
on input
reaches state
in exactly 100 steps
is not recursive
contains at least 21 members
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 36
Open questionCSMCQ2 marksNeeds review
Consider the following problems.
denotes the language generated by a grammar
.
denotes the language accepted by a machine
.(I) For an unrestricted grammar
and a string
, whether
(II) Given a Turing machine
, whether
is regular
(III) Given two grammars
and
, whether
(IV) Given an NFA
, whether there is a deterministic PDA
such that
and
accept the same language.Which one of the following statements is correct?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 39
Open questionCSMCQ2 marksNeeds review
Let
and
be finite alphabets and let
be a symbol outside both
and
. Let
be a total function from
to
. We say
is computable if there exists a Turing machine
which given an input
in
, always halts with
on its tape. Let
denote the language
. Which of the following statements is true:Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 41
Open questionCSMCQ2 marksNeeds review
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer