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
1
answer
1
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
2 days
ago
in
Theory of Computation
by
Sumit Singh Chauhan
Junior
(
855
points)

18
views
theoryofcomputation
decidability
0
votes
1
answer
2
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
3 days
ago
in
Theory of Computation
by
Sumit Singh Chauhan
Junior
(
855
points)

13
views
theoryofcomputation
regularlanguages
decidability
+1
vote
1
answer
3
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
(
179
points)

26
views
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
0
answers
4
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
(
179
points)

11
views
theoryofcomputation
decidability
turingmachine
+1
vote
1
answer
5
#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.1k
points)

39
views
decidability
cfg
0
votes
0
answers
6
self doubt
is p and np problem are in syllabus in toc ???
asked
Jul 26
in
Theory of Computation
by
vijju532
(
369
points)

41
views
decidability
+2
votes
1
answer
7
#undecidability
why recursive enumerable languages does not satisfy the complementation property ???
asked
Jul 24
in
Theory of Computation
by
vijju532
(
369
points)

50
views
decidability
+1
vote
0
answers
8
self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
asked
Jul 24
in
Theory of Computation
by
Vegeta
(
183
points)

82
views
decidability
theoryofcomputation
turingmachine
+3
votes
1
answer
9
Decidability Vs SemiDecidability Vs Undecidability Self Doubt
asked
Jul 12
in
Theory of Computation
by
Balaji Jegan
Active
(
1.4k
points)

469
views
decidability
theoryofcomputation
turingmachine
0
votes
0
answers
10
Semidecidability Vs Undecidability
Let L1 and L2 be 2 languages generated by an Unrestricted Grammar. I know that none of the following are decidable. But which of them are semidecidable and which are Undecidable? 1. Whether L1 is Finite? 2. Whether L1 is Regular? 3. Whether L1 is Equivalent to ... complete? 8. Whether L1 is a subset of L2? 9. Whether (∑*  L1) is finite? 10. Whether L1 is Empty?
asked
Jun 20
in
Theory of Computation
by
Balaji Jegan
Active
(
1.4k
points)

120
views
theoryofcomputation
decidability
0
votes
0
answers
11
Decidable
All $P$, $NP$ and $NPC$ problems are turing decidable problems. $CFLs$ are in $NP$ area and $CFL's$ are not closed under intersection and complementation. So does it mean that $CFL's$ are undecidable under intersection and complementation. If $CFL$ is undecidable on intersection and complementation then how $NP$ problems can be turing decidable?
asked
Jun 18
in
Theory of Computation
by
!KARAN
(
415
points)

32
views
theoryofcomputation
pnpnpcnph
decidability
0
votes
1
answer
12
Decidable or not
Now define D , the diagonal set of strings: $D=\left \{ w\epsilon \Sigma ^{*} \right \}$ where $w$ is not in $f\left ( w \right )$ Call the correspondence $f$ is countable set $\Sigma ^{*}$ For example $f\left ( \varepsilon \right )=L_{0}$ ,i.e. ... ( 1 \right )=L_{2}$ for all even length string of infinite language etc. Now, the question is 1) is D countable? 2) is D decidable?
asked
Jun 15
in
Theory of Computation
by
srestha
Veteran
(
91.8k
points)

38
views
decidability
theoryofcomputation
+1
vote
2
answers
13
Decidable
1)Let G be CFG. Whether L(G) is CFL. Q)Is it decidable or not? 2)Let G be CFG and unambiguous. Whether L(G) is CFL. Q)Is it decidable or not?
asked
Jun 1
in
Theory of Computation
by
srestha
Veteran
(
91.8k
points)

129
views
decidability
theoryofcomputation
turingmachine
0
votes
1
answer
14
TOC Decidability Theory
Which of the following problems is solvable? a) Writing a universal Turing machine b) Determining if an arbitrary Turing machine is a Universal Turing Machine c) Determining if a universal Turing Machine can be written in fewer than k instructions for some k d) Determining if a universal Turing Machine and some input will halt
asked
Apr 25
in
Theory of Computation
by
gauravkc
Loyal
(
6.1k
points)

183
views
decidability
theoryofcomputation
turingmachine
+2
votes
2
answers
15
what type of language
{$<M>\mid M$ is a $TM$ that doesn't accept any even number} what type of language is it? Recursively enumerable Recursive Not recursively enumerable none of the above
asked
Mar 15
in
Theory of Computation
by
Sambit Kumar
Active
(
4.1k
points)

129
views
decidability
turingmachine
theoryofcomputation
0
votes
1
answer
16
Self Doubt on Decidability
Here in this video https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87 professor is explaining that Turing Machine that accept something is recursively enumerable. We would run multiple inputs on turning machine in parallel using ... there are even two strings that are being accepted won't we get to know using the same method ?
asked
Mar 4
in
Theory of Computation
by
Jeevesh
(
183
points)

93
views
theoryofcomputation
turingmachine
decidability
shaisimonson
0
votes
0
answers
17
#TOC Undecidability
In this lecture by Shai Simonson : https://youtu.be/77OG6ziPMu4 At 33:04 he mentions that "A = CFL that does not accept $\sum^*$ " is Undecidable. Also, we already know that "A' = CFL that accept $\sum ^*$ " is Undecidable as well. so if A and A' both are Recursively Enumerable sets, then wouldn't that make A a recursive set ?
asked
Feb 23
in
Theory of Computation
by
Abbas2131
Active
(
1.8k
points)

46
views
theoryofcomputation
decidability
contextfreelanguages
+7
votes
3
answers
18
GATE201836
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 \: \epsilon \: L(G)$ Given a Turing machine $M$, ... 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
Feb 14
in
Theory of Computation
by
gatecse
Boss
(
18.1k
points)

1.9k
views
gate2018
theoryofcomputation
decidability
easy
+2
votes
1
answer
19
Decidability
L={R  R is a regular expression, with atleast one w belongs to L(R), i.e. 101 is substring of w} Which one true? a)L is decidable b) L is undecidable c)L is partially decidable
asked
Jan 27
in
Theory of Computation
by
srestha
Veteran
(
91.8k
points)

83
views
decidability
theoryofcomputation
+1
vote
1
answer
20
decidability
Is the following problem decidable: 1. Given a deterministic contextfree grammar G, is L(G) = Σ* for some alphabet Σ ? Please also provide explaination.
asked
Jan 26
in
Theory of Computation
by
Aakanchha
Junior
(
727
points)

106
views
decidability
theoryofcomputation
+1
vote
0
answers
21
Rice's Theorem
What is monotonic and nonmonotonic property. Please explain the second postulate of Rice's Theorem.
asked
Jan 23
in
Theory of Computation
by
Sumaiya23
Active
(
1.4k
points)

55
views
ricetheorem
decidability
theoryofcomputation
selfdoubt
turingmachine
+2
votes
0
answers
22
[Made Easy Test Series] TOC
Consider the following langauge over Σ = {0, 1}: L = {<M>M is TM that accept all strings of length atmost 5} Which of the following is true? A.) Decidable and REC B.) Undecidable and RE C.) Undecidable and non RE D.) Decidable but RE
asked
Jan 22
in
Theory of Computation
by
ashish pal
Active
(
1.1k
points)

114
views
madeeasytestseries
theoryofcomputation
decidability
+1
vote
1
answer
23
decidable problem
Let L be a DCFL and R is a regular language. Consider the below given problems. P: Is L=R ? Q: Is R ⊆L ? Discuss decidablity of P and Q.
asked
Jan 21
in
Theory of Computation
by
MIRIYALA JEEVAN KUMA
Active
(
1.8k
points)

101
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
2
answers
24
Intersection of two Recursive languages are of same type or not. Is it decidable or undecidable?
asked
Jan 18
in
Theory of Computation
by
nikhil_cs
Junior
(
647
points)

126
views
recursiveandrecursivelyenumerablelanguages
decidability
+2
votes
2
answers
25
Undecidability Confusion
I was Studying About Undecidability on GateCSE. I am facing a doubt that : L = {<M>  M accepts "1"} L is set of String & each String is an Encoding of TM & TM accepts 1 L = {<M>  L(M) = {1}} Given a Input Program ... really is difference between both of them ? Can you definition of 2 in words like " L is set of String ............"
asked
Jan 13
in
Theory of Computation
by
yogi_p
Active
(
1.7k
points)

103
views
theoryofcomputation
decidability
ricetheorem
+2
votes
0
answers
26
MadeEasy Test Series
Consider the following language over Σ = {0, 1}:L = {<M>M is TM that accept all strings of length at most 5} Which of the following is true? (A) Decidable and REC (B) Undecidable and RE (C) Undecidable and non RE (D) Decidable but RE
asked
Jan 12
in
Theory of Computation
by
Bhavya Bhatia
(
407
points)

264
views
madeeasytestseries
decidability
turingmachines
+3
votes
0
answers
27
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
asked
Jan 10
in
Theory of Computation
by
Nymeria
(
415
points)

137
views
decidability
contextfreelanguage
turingmachine
reduction
+2
votes
0
answers
28
undecidability
Define languages L0 and L1 as follows : L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halt on w} Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a ... an acceptor for L as even when L0 is RE L1 is not RE but can anyone explain me what about L COMPLEMENT what is the language ??
asked
Jan 9
in
Theory of Computation
by
Venkat Sai
Active
(
3.3k
points)

94
views
theoryofcomputation
decidability
ricetheorem
+2
votes
1
answer
29
Test Series
Explain please. Answer given is D
asked
Jan 2
in
Theory of Computation
by
Anmol_Binani
Junior
(
621
points)

89
views
theoryofcomputation
decidability
+1
vote
1
answer
30
not partially decidable
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?
asked
Jan 2
in
Theory of Computation
by
Mk Utkarsh
Boss
(
14k
points)

63
views
theoryofcomputation
decidability
Page:
1
2
3
4
5
6
...
8
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
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged decidability
Recent Blog Comments
gate overflow books are awesome; every one should ...
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
38,094
questions
45,587
answers
132,148
comments
49,124
users