The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged decidability
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
0
votes
1
answer
1
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
asked
Nov 14, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

72
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
2
Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
asked
Nov 1, 2018
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.3k
points)

107
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
0
answers
3
Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
asked
Nov 1, 2018
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.3k
points)

64
views
decidability
theoryofcomputation
contextfreelanguage
0
votes
0
answers
4
Reducibility Problem
Consider 2 problems X & Y. Now if X is reducible to Y.What does this mean.please explain with an example.
asked
Oct 30, 2018
in
Theory of Computation
by
Lovejeet Singh
(
15
points)

50
views
reducibilty
decidability
theoryofcomputation
0
votes
0
answers
5
Undecidability
L1:{<M>  there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it nontrivial then please explain why is that so. According to my understanding, nontrivial properties ... it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked
Oct 30, 2018
in
Theory of Computation
by
Swapnil Naik
Active
(
3k
points)

55
views
theoryofcomputation
ricetheorem
turingmachine
decidability
0
votes
0
answers
6
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
asked
Oct 29, 2018
in
Theory of Computation
by
aditi19
Active
(
3.7k
points)

65
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
7
turing machine decidability
Given a turing machine M ,state q, and string 'w' whether M ever moves its head to the left when started with input w is decidable or undecidable ? explain ?
asked
Oct 28, 2018
in
Theory of Computation
by
Gurdeep Saini
Loyal
(
9.5k
points)

48
views
decidability
+4
votes
1
answer
8
DECIDABILITY
L = {<M>  L(M) = {1}} L = {<M>  L(M) is {} } L = {<M>  L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
asked
Oct 16, 2018
in
Theory of Computation
by
Smishra95
Active
(
1.3k
points)

89
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+1
vote
2
answers
9
Decidability
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ Is $L_1$ RE or not RE?
asked
Oct 8, 2018
in
Theory of Computation
by
Somoshree Datta 5
Active
(
4.9k
points)

292
views
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
1
answer
10
doubt
What is semi and Partially decidable...and how we know
asked
Oct 1, 2018
in
Theory of Computation
by
bhavnakumrawat5
(
165
points)

77
views
decidability
0
votes
1
answer
11
Decidability
Let A, B, C and D are problems. Consider the following polynomial reductions to known about the problem B. (i) AB (A is reducible to B) (ii) C D (iii) B D Find the correct statement from the following 1.. if A is decidable, B is decidable 2. if D is undecidable, B is undecidable 3. if C is decidable, B is decidable 4. if A is undecidable, B is undecidable
asked
Sep 26, 2018
in
Theory of Computation
by
aditi19
Active
(
3.7k
points)

98
views
decidability
0
votes
0
answers
12
undecidability
Writes Non Blank: Given a turing machine T, does it ever writes a nonblank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then ... is a nontrivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked
Sep 21, 2018
in
Theory of Computation
by
aambazinga
Active
(
3.2k
points)

49
views
theoryofcomputation
decidability
ricetheorem
turingmachine
0
votes
1
answer
13
Decidability12.9.5
Let $L_1$ be a regular language and G be a contextfree grammar. Show that the problem "$L_1 \subseteq L(G)$" is undecidable.
asked
Sep 17, 2018
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.9k
points)

78
views
decidability
theoryofcomputation
0
votes
2
answers
14
Decidability
Let M1 be a Turing machine and M2 be a finite automaton. Is the problem, whether M1 and M2 accept the same language decidable? An elaborative answer with proof is most welcome.
asked
Sep 17, 2018
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.9k
points)

104
views
decidability
theoryofcomputation
0
votes
0
answers
15
TM that rejects input string x
$D = \left \{ <M> \mid \ M \text{ is a TM that rejects the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
asked
Sep 15, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.6k
points)

83
views
decidability
0
votes
1
answer
16
TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
asked
Sep 15, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.6k
points)

162
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
17
Decidable / Undecidable (Acceptance of CFL)
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
asked
Sep 15, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.6k
points)

55
views
decidability
theoryofcomputation
0
votes
1
answer
18
Decidable / Undecidable
Given a regular language, does the language contain any string at all. Given a regular language, does the language contain infinite number of strings. Given a recursive language, does the language contain infinite number of strings. Given a recursive language, does the language contain any string at all.
asked
Sep 15, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.6k
points)

50
views
decidability
theoryofcomputation
+2
votes
1
answer
19
Decidability (Acceptance problem)
Whether the given languages are recursive, recursively enumerable or non RE 1) $L = \left \{ <M>  <M> \ accepts \ all \ strings \ of \ length \ at \ most \ 5 \right \}$ 2) $L = \left \{ <M>  <M> \ accepts \ strings \ of \ length \ at \ most \ 5 \right \}$
asked
Sep 14, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.6k
points)

193
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
20
Turing machine
Consider <M> be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M>  M is a TM that halts on all the input and L(M) = L' for some Undecidable language L' } then L is ? A. Decidable and Recursive B. Decidable and Non recursive C. Undecidable and RE D. Undecidable and Non RE
asked
Sep 9, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.6k
points)

37
views
turingmachine
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
0
answers
21
Relationship b/w closure and decidability?
Is there any relationship b/w closure and decidability? Thanks
asked
Sep 9, 2018
in
Theory of Computation
by
surbhijain93
(
219
points)

43
views
theoryofcomputation
decidability
closureproperty
0
votes
0
answers
22
self doubt
CAN SOMEONE EXPLAIN ME WITH AN EXAMPLE THAT WHY DCFL CLOSED UNDER COMPLEMENATION AND CFL NOT CLOSED UNDER COMPLEMENATION?
asked
Sep 9, 2018
in
Theory of Computation
by
sushmita
Boss
(
16.4k
points)

31
views
theoryofcomputation
closureproperty
decidability
0
votes
0
answers
23
TOC Undecidability
asked
Sep 9, 2018
in
Theory of Computation
by
sidlewis
Junior
(
801
points)

58
views
theoryofcomputation
decidability
ricetheorem
contextfreelanguages
turingmachine
0
votes
0
answers
24
TOC Decidability
How can we say that any two disjoint coturing recognisable languages are seperable by some Decidability language?
asked
Sep 8, 2018
in
Theory of Computation
by
aambazinga
Active
(
3.2k
points)

38
views
theoryofcomputation
decidability
coturingrecognizable
0
votes
1
answer
25
TOC DECIDABILITY
Let E={<M> M is a DFA that accepts some strings with more 1's than 0's} Show that E is decidable. How can E be decidable. How can a DFA compare between number of 1's and 0's. From the question I know that it's not talking about all, but some. The things is even some should not be decidable. isn't it?
asked
Sep 8, 2018
in
Theory of Computation
by
aambazinga
Active
(
3.2k
points)

59
views
theoryofcomputation
decidability
finiteautomata
0
votes
1
answer
26
Difference between computability and decidability
Hi, Could someone please tell the difference between computability and decidability? Thanks
asked
Sep 7, 2018
in
Theory of Computation
by
surbhijain93
(
219
points)

156
views
decidability
turingmachine
0
votes
0
answers
27
Ace Test Series: Theory Of Computation  Decidablity
Can someone explain this problem?
asked
Sep 4, 2018
in
Theory of Computation
by
Kalpataru Bose
(
349
points)

150
views
acetestseries
theoryofcomputation
decidability
0
votes
0
answers
28
Gateoverflow questions
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of them have different answers and I am not able to decide which one is correct. https://gateoverflow.in/82703/tocturingmachine https://gateoverflow.in/98850/turingmachine
asked
Sep 2, 2018
in
Theory of Computation
by
Swapnil Naik
Active
(
3k
points)

58
views
turingmachine
decidability
0
votes
0
answers
29
Decidability
Ans. D
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.6k
points)

38
views
decidability
theoryofcomputation
turingmachine
0
votes
1
answer
30
Turing Decidable
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.6k
points)

79
views
theoryofcomputation
turingmachine
decidability
Page:
« prev
1
2
3
4
5
6
7
8
9
...
12
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
Recent Posts
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
@Anmol 300 books will be dispatched this month...
Dear Respected Sir, If I prebook now i.e.22...
Can you check your Spam too? Address confirmation...
yeah me too. I did not get the address...
49,811
questions
54,530
answers
188,403
comments
75,483
users