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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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
0
answers
1
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
13 hours
ago
in
Theory of Computation
by
Smishra95
Active
(
1.2k
points)

9
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+1
vote
2
answers
2
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
in
Theory of Computation
by
Somoshree Datta 5
Active
(
2.2k
points)

235
views
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
1
answer
3
doubt
What is semi and Partially decidable...and how we know
asked
Oct 1
in
Theory of Computation
by
bhavnakumrawat5
(
189
points)

50
views
decidability
0
votes
1
answer
4
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
in
Theory of Computation
by
aditi19
Junior
(
849
points)

46
views
decidability
0
votes
0
answers
5
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
in
Theory of Computation
by
aambazinga
Active
(
1.1k
points)

18
views
theoryofcomputation
decidability
ricetheorem
turingmachine
0
votes
1
answer
6
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
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
13.8k
points)

39
views
decidability
theoryofcomputation
0
votes
2
answers
7
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
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
13.8k
points)

54
views
decidability
theoryofcomputation
0
votes
0
answers
8
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.7k
points)

54
views
decidability
0
votes
1
answer
9
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.7k
points)

99
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
10
Decidable / Undecidable (Acceptance of CFL)
asked
Sep 15
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.7k
points)

24
views
decidability
theoryofcomputation
0
votes
1
answer
11
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.7k
points)

23
views
decidability
theoryofcomputation
+2
votes
1
answer
12
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.7k
points)

126
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
13
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
in
Theory of Computation
by
Na462
Loyal
(
6.4k
points)

19
views
turingmachine
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
0
answers
14
Relationship b/w closure and decidability?
asked
Sep 9
in
Theory of Computation
by
surbhijain93
(
131
points)

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

17
views
theoryofcomputation
closureproperty
decidability
0
votes
0
answers
16
TOC Undecidability
asked
Sep 9
in
Theory of Computation
by
sidlewis
(
343
points)

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

14
views
theoryofcomputation
decidability
coturingrecognizable
0
votes
1
answer
18
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
in
Theory of Computation
by
aambazinga
Active
(
1.1k
points)

31
views
theoryofcomputation
decidability
finiteautomata
0
votes
0
answers
19
Difference between computability and decidability
asked
Sep 7
in
Theory of Computation
by
surbhijain93
(
131
points)

32
views
decidability
turingmachine
0
votes
0
answers
20
test series
Can someone explain this problem?
asked
Sep 4
in
Theory of Computation
by
Kalpataru Bose
(
465
points)

75
views
testseries
madeeasytestseries
testbooktestseries
theoryofcomputation
decidability
turingmachine
acetestseries
0
votes
0
answers
21
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
in
Theory of Computation
by
Swapnil Naik
Active
(
1.3k
points)

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

26
views
decidability
theoryofcomputation
turingmachine
0
votes
1
answer
23
Turing Decidable
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
6.4k
points)

48
views
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
24
Decidability
Ans. B
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
6.4k
points)

28
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
Doubt TOC
which of the following is/are decidable? 1)for some input if an arbitrary TM makes 5 moves. 2) whether an arbitary TM halts within 5 steps 3) whether an arbitary TM prints some non blank character 4)the set of codes for TM that never make a left move. 5)an arbitrary TM halts after 100 steps 6)a TM prints a specific letter 7) a turing machine computes the product of two numbers.
asked
Aug 24
in
Theory of Computation
by
Sumit Singh Chauhan
Active
(
1.3k
points)

41
views
theoryofcomputation
decidability
turingmachine
0
votes
1
answer
26
TOC  Doubt
Choose the correct statement. A class of languages that is closed under A. Intersection and complementation has not to be closed under union B. Union and complementation has to be closed uneer intersection C. Union and intersection has to be closed under complementation. D. Both B and C
asked
Aug 15
in
Theory of Computation
by
Sumit Singh Chauhan
Active
(
1.3k
points)

44
views
theoryofcomputation
decidability
0
votes
1
answer
27
TOC  Doubt
As we know that the regular languages are closed under complement. That means if L is regular than it's complement will also be regular. What about the non regular languages? Are they closed under complement? Can we say that if L is non regular than it's complement will also be not regular? Please explain.
asked
Aug 15
in
Theory of Computation
by
Sumit Singh Chauhan
Active
(
1.3k
points)

18
views
theoryofcomputation
regularlanguages
decidability
+1
vote
1
answer
28
TOC decidability
Let <M> be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M>  M is TM on input w will visit some state P}. The language L is (a) Decidable (b) Undecidable but partially decidable (c) Undecidable and not even partially decidable (d) Not a decision problem
asked
Aug 10
in
Theory of Computation
by
manisha11
Junior
(
981
points)

53
views
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
0
answers
29
Theory Of Computation , Decidability
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True? (a) If L ≤ pL’ and L’ is semidecidable then L is semidecidable. (b) If L ≤ pL’ and L is RE then L’ is RE. (c) If L ≤ pL’ and L is decidable then L’ decidable. (d) If L ≤ pL’ and L is recursive. Solution: Option (a) PLEASE Explain
asked
Aug 10
in
Theory of Computation
by
manisha11
Junior
(
981
points)

25
views
theoryofcomputation
decidability
turingmachine
+1
vote
1
answer
30
#Self doubt
Whether a given contextfree language is regular is decidable or undecidable? Prove your answer!
asked
Jul 29
in
Theory of Computation
by
himgta
Active
(
1.7k
points)

48
views
decidability
cfg
Page:
1
2
3
4
5
6
...
9
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged decidability
Recent Blog Comments
@sahil you can see my response sheet...
How many tests will be uploaded before gate 19?
@IITDELHIVISHAL Yes, it will work. Make your...
sir if watch& making notes from quality videos...
yes! those will be available on GO,no need to pay
40,845
questions
47,506
answers
145,764
comments
62,261
users