Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions tagged decidability
0
votes
0
answers
Made easy test series
Consider the following problems and select the problem which is recursively enumerable but not recursive. (MSQ type) 1 . Whether a given Turing machine accepts nonempty language. 2. Whether a given Turing machine accepts finite language . 3. Whether a given Turing machine accepts at most 10 strings 4. Whether a given Turing machine accepts at least 10 strings.
asked
Feb 4
in
Theory of Computation
by
gajendercse
(
41
points)

44
views
decidability
selfdoubt
0
votes
0
answers
self doubt  decidability
L={<M> M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here
asked
Feb 1
in
Theory of Computation
by
Abhineet Singh
(
23
points)

21
views
decidability
toclanguages
0
votes
0
answers
Self doubt on decidability of turing machine and dfa
asked
Jan 5
in
Theory of Computation
by
meivinay
(
5
points)

58
views
decidability
turingmachine
selfdoubt
0
votes
0
answers
applied gate test
Q.7)Max Marks: 1Subject: Theory of Computation A aii; bi; ciii B aii; biii; ci Correct Option  Attempted Solution: (B) C aiii; bi; cii D ai; bii; ciii
asked
Nov 23, 2020
in
Theory of Computation
by
Mayur Rasadiya
(
5
points)

26
views
decidability
0
votes
0
answers
#Decidability
Can anyone tell me how to approach the problems like 1) Is Language generated by CFG subset of langauage generated by regular grammar is decidable?? 2)membership of cfg,emptiness problems....???(Not just these two but how to approach such type of problems)?????
asked
Sep 14, 2020
in
Theory of Computation
by
Jithendra319
(
13
points)

26
views
decidability
0
votes
1
answer
self doubt on p and np problem
does P=NP ? a)decidable b)undecidable also please explain why it is decidable or undecidable.
asked
Aug 19, 2020
in
Theory of Computation
by
abhijeet at
(
9
points)

51
views
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
#made easy test series
Let L1 be a decidable language and L2 be a turing recognizable language but not decidable language .consider the following statements: L2\L1 is a turing recognizable language. L1\L2 is a decidable language L2\L1 is a decidable language L1\L2 is turing recognizable language the number of correct statements is/are:
asked
Aug 1, 2020
in
Theory of Computation
by
404 found
(
37
points)

28
views
madeeasytestseries
decidability
0
votes
0
answers
Theory Of Computation, Decidability, Rice's Theorem
asked
Jul 30, 2020
in
Theory of Computation
by
pranavsettaluri9
(
5
points)

14
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
ricestheorem
0
votes
0
answers
GATE2017139 Video Solution
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input ... $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

12
views
gate20171
theoryofcomputation
decidability
difficult
videosolution
0
votes
0
answers
GATE201836 Video Solution
Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$. L(M) denotes the language accepted by a machine $M$. For an unrestricted grammar $G$ and a string $w$, whether $w \in L(G)$ ... is correct? Only I and II are undecidable Only II is undecidable Only II and IV are undecidable Only I, II and III are undecidable
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

13
views
gate2018
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE201017 Video Solution
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2  L_1 \:\text{is recursively enumerable.}$ ... $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

4
views
gate2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
normal
videosolution
0
votes
0
answers
GATE2015221 Video Solution
Consider the following statements. The complement of every Turing decidable language is Turing decidable There exists some language which is in NP but is not Turing decidable If L is a language in NP, L is Turing decidable Which of the above statements is/are true? Only II Only III Only I and II Only I and III
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

5
views
gate20152
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE20012.7 Video Solution
Consider the following problem $X$. Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$? Which of the ... ? $X$ is decidable $X$ is undecidable but partially decidable $X$ is undecidable and not even partially decidable $X$ is not a decision problem
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

10
views
gate2001
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE200810 Video Solution
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given contextfree language is regular Whether two pushdown automata accept the same language Whether a given grammar is contextfree I and II I and IV II and III II and IV
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

8
views
gate2008
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE200545 Video Solution
Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE? $P_3$ is decidable if $P_1$ is reducible to $P_3$ $P_3$ is undecidable if $P_3$ is reducible to $P_2$ $P_3$ is undecidable if $P_2$ is reducible to $P_3$ $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate2005
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE2016117 Video Solution
Which of the following decision problems are undecidable? Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$ Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ? Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$? Given a TM $M$, is $L(M)=\Phi$ ? I and IV only II and III only III and IV only II and IV only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

7
views
gate20161
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE19903vii Video Solution
Choose the correct alternatives (More than one may be correct). It is undecidable whether: An arbitrary Turing machine halts after $100$ steps. A Turing machine prints a specific letter. A Turing machine computes the products of two numbers None of the above.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

9
views
gate1990
normal
theoryofcomputation
decidability
videosolution
0
votes
0
answers
GATE20002.9 Video Solution
Consider the following decision problems: $(P1):$ Does a given finite state machine accept a given string? $(P2):$ Does a given context free grammar generate an infinite number of strings? Which of the following statements is true? Both$(P1)$ and $(P2)$ are decidable Neither $(P1)$ nor $(P2)$ is decidable Only $(P1)$ is decidable Only $(P2)$ is decidable
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate2000
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE201224 Video Solution
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a contextfree language, then, is $\bar{L}$ also contextfree? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

8
views
gate2012
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE201341 Video Solution
Which of the following is/are undecidable? $G$ is a CFG. Is $L(G) = \phi$? $G$ is a CFG. Is $L(G) = \Sigma^*$? $M$ is a Turing machine. Is $L(M)$ regular? $A$ is a DFA and $N$ is an NFA. Is $L(A) = L(N)$? 3 only 3 and 4 only 1, 2 and 3 only 2 and 3 only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

7
views
gate2013
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE2017241 Video Solution
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? Given a regular ... string $w$, is $w \in L(M)$? I and IV only II and III only II, III and IV only III and IV only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

7
views
gate20172
theoryofcomputation
decidability
videosolution
0
votes
0
answers
GATE200352 Video Solution
Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{1}$ be also polynomial ... $\in NP$ and $L_2$ $\in P$ $L_1$ is undecidable and $L_2$ is decidable $L_1$ is recursively enumerable and $L_2$ is recursive
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

9
views
gate2003
theoryofcomputation
normal
decidability
videosolution
0
votes
0
answers
GATE19893iii Video Solution
Answer the following questions: Which of the following problems are undecidable? Membership problem in contextfree languages. Whether a given contextfree language is regular. Whether a finite state automation halts on all inputs. Membership problem for type $0$ languages.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

8
views
gate1989
normal
theoryofcomputation
decidability
videosolution
0
votes
0
answers
GATE19976.5 Video Solution
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is nonempty
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

5
views
gate1997
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE2015353 Video Solution
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true? $\text{ if } L_4 \in P, \text{ then } L_2 \in P$ ... $\text{ if } L_4 \in P, \text{ then } L_3 \in P$ II only III only I and IV only I only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

7
views
gate20153
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE2014335 Video Solution
Which one of the following problems is undecidable? Deciding if a given contextfree grammar is ambiguous. Deciding if a given string is generated by a given contextfree grammar. Deciding if the language generated by a given contextfree grammar is empty. Deciding if the language generated by a given contextfree grammar is finite.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate20143
theoryofcomputation
contextfreelanguages
decidability
normal
videosolution
0
votes
0
answers
GATE19961.9 Video Solution
Which of the following statements is false? The Halting Problem of Turing machines is undecidable Determining whether a contextfree grammar is ambiguous is undecidable Given two arbitrary contextfree grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$ Given two regular grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate1996
theoryofcomputation
decidability
easy
videosolution
0
votes
0
answers
GATE20076 Video Solution
Which of the following problems is undecidable? Membership problem for CFGs Ambiguity problem for CFGs Finiteness problem for FSAs Equivalence problem for FSAs
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

5
views
gate2007
theoryofcomputation
decidability
normal
videosolution
0
votes
0
answers
GATE20017 Video Solution
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

17
views
gate2001
theoryofcomputation
decidability
turingmachine
easy
descriptive
videosolution
0
votes
0
answers
GATE200214 Video Solution
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs a}$ $1\}$ ... second step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

6
views
gate2002
theoryofcomputation
decidability
normal
turingmachine
descriptive
difficult
videosolution
+1
vote
1
answer
GATE2020CS26 Video Solution
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

28
views
gate2020cs
theoryofcomputation
decidability
videosolution
0
votes
0
answers
GATE199511 Video Solution
Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below. $L$ is in NP and For every $n$, there is exactly one string of length $n$ that belongs to $L$. Let $L^c$ be the complement of $L$ over $\Sigma^*$. Show that $L^c$ is also in NP.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

7
views
gate1995
theoryofcomputation
normal
decidability
videosolution
0
votes
0
answers
GATE19872l Video Solution
State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

14
views
gate1987
decidability
videosolution
0
votes
0
answers
GATE19872m Video Solution
State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

5
views
gate1987
theoryofcomputation
turingmachine
decidability
videosolution
0
votes
0
answers
GATE19882viii Video Solution
State the halting problem of the Turing machine.
asked
Apr 18, 2020
in
Theory of Computation
by
admin
(
573
points)

4
views
gate1988
theoryofcomputation
descriptive
decidability
videosolution
0
votes
0
answers
TOC : Ace test series (Semi decidable)
asked
Jan 30, 2020
in
Theory of Computation
by
Chirag Shilwant
(
191
points)

41
views
aceacademytestseries
theoryofcomputation
recursiveenumurablelanguage
decidability
0
votes
0
answers
GATE 2015 Question
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3SAT and 3 SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement? (A) Q1 is in NP, Q2 in NPhard (B) Q2 is in NP, Q1 is NPhard (C) Both Q1 and Q2 are in NP (D) Both Q1 and Q2 are NPhard
asked
Jan 20, 2020
in
Theory of Computation
by
veenashiva18
(
5
points)

44
views
theoryofcomputation
decidability
0
votes
0
answers
Self Doubts #Decidablity
I am looking the explanation of the below mentioned being decidable / Undecidable. (Given : Defination of TM in binary) Turing machine's control head move left/ right once, for a given input . Turing machine's control head move left/ right any ... answer vary from 2nd point ?) Turing machine replaces at least one character / exactly k (finite) characters in the input.
asked
Jan 20, 2020
in
Theory of Computation
by
dr_Jackal
(
5
points)

17
views
decidability
automata
turingmachine
0
votes
1
answer
SINGLE SUBJECT : THEORY OF COMPUTATION  Q2
Let L = $\{\text{Language of CFG's that are ambiguous} \}.$ Let $\text{L}$' be a compliment of language L. Which of the following is true? $\text{L is RE and L' is RE}$ $\text{L is not RE and L' is RE}$ ... has an ambiguous grammar. Hence every CFL which is nonempty will be in $L$. So L is a set of all nonempty CFL's. How to proceed?
asked
Jan 4, 2020
in
Theory of Computation
by
Mk Utkarsh
(
957
points)

80
views
theoryofcomputation
decidability
madeeasytestseries
0
votes
0
answers
ACe mock test 4 Q54
Please explain the meaning of the question
asked
Jan 4, 2020
in
Theory of Computation
by
ssap09
(
13
points)

16
views
aceacademytestseries
theoryofcomputation
decidability
Page:
1
2
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
9,106
questions
3,157
answers
14,595
comments
95,958
users