The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
0
answers
1
#TOC #GeneralGuidance
I am new to the topic of TOC and finding it difficult to develop intuition for questions. Though,I am good with Mathematics and someone told TOC is mathematical concept. How should I study TOC specifically?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
345
points)

33
views
theoryofcomputation
finiteautomata
regularexpressions
decidability
+1
vote
0
answers
2
GO_DecidabilitySlides
This is from GO Decidability slides. I have a doubt with 3 & 4 which is saying every TM ACCEPT L since accepted implies that it rejects all which is not part of language.Why we are using ACCEPTED instead of the word RECOGNISED?
asked
Jan 27
in
Theory of Computation
by
Abbas Ahmad
(
115
points)

41
views
decidability
selfdoubt
0
votes
1
answer
3
Turing Machines Theory
What is the difference between Turing Recognizable and Turing Decidable? Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

51
views
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
4
Reducible language ( Decidability)
asked
Jan 21
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

55
views
theoryofcomputation
decidability
0
votes
2
answers
5
Gateforum mock 2
asked
Jan 20
in
Theory of Computation
by
Prince Sindhiya
Loyal
(
6.2k
points)

61
views
decidability
0
votes
0
answers
6
Decidability
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$ I was unable to get proof given in pdf above.Can anyone explain, if someone got it.
asked
Jan 13
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.5k
points)

57
views
decidability
theoryofcomputation
0
votes
1
answer
7
Decidability
Let L be a DCFL and R is a regular language. Consider the below given problems. P : Is L ≠ R? Q : is R ⊂ L? Choose the correct option. Both problems P and Q are decidable. Both problems P and Q are undecidable. Problem Q is decidable and P is ... DCFL's, i.e when both languages are DCFL's. How do I analyze decidablity for different languages? In this case, for a RL and DCFL.
asked
Jan 9
in
Theory of Computation
by
utkarshkosta
(
33
points)

58
views
decidability
theoryofcomputation
0
votes
0
answers
8
toc(undecidability)
does intersection and complement problem of CSL language follow closure property? does intersection and complement problem of CSL language are decidable?
asked
Jan 9
in
Theory of Computation
by
harsh yadav
(
111
points)

21
views
decidability
0
votes
0
answers
9
© 2016 Pearson Education, Inc., Hoboken
What will be the bias used in a word addressing computer if the number of bits for exponent are 9? If 9 bits are used for the representation of a number, then what will be the maximum number in signed number range if the numbers are represented in 2’s complement?
asked
Jan 8
in
CO & Architecture
by
Mohamad Al Rebdawi
(
7
points)

23
views
computernetworks
theoryofcomputation
decidability
usermod
0
votes
0
answers
10
TOC(Undecidability)
L1 = { <M>  M halts on $\epsilon$ } L2 = { <M>  $\epsilon$ $\in$ L(M) } Which one is RE or not RE
asked
Jan 8
in
Theory of Computation
by
jatin khachane 1
Loyal
(
6.4k
points)

81
views
theoryofcomputation
decidability
+1
vote
0
answers
11
RE or non RE
CONSIDER THE FLLOWING LANGUAGE L={<M> M is a TM and L(M)=empty} Which of the following is true? a Decidable REC B Undecidable and RE cUndecidable and non RE d Decidable but RE
asked
Jan 8
in
Theory of Computation
by
bts1jimin
(
245
points)

81
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
12
Decidability
Consider the following language over $\sum=\{0,1\}$ $L=\{<M>$ M is a turing machine that accepts all strings of length atmost 5 $\}$ Since, this is a nontrivial property of TM, so surely it is undecidable. Now, Applying Rice’s Theorem part 2, $T_{yes}=\{0,1\}$ and $T_{no}=\sum^*$ and $T_{yes} \subset T_{no}$ so this is NOT RE. Have I correctly applied property 2?
asked
Jan 3
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.5k
points)

82
views
decidability
theoryofcomputation
0
votes
0
answers
13
TOC Doubt
CFG G=(N,Σ,P,S) and a string x∈Σ∗, does x∈L(G)} ? Is it Decidable?
asked
Jan 2
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.3k
points)

49
views
theoryofcomputation
decidability
0
votes
1
answer
14
Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.
asked
Dec 30, 2018
in
Theory of Computation
by
Ayan21
(
107
points)

53
views
decidability
theoryofcomputation
contextfreelanguage
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
15
self doubt
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
asked
Dec 27, 2018
in
Theory of Computation
by
MRINMOY_HALDER
Junior
(
625
points)

50
views
theoryofcomputation
decidability
0
votes
0
answers
16
Decidability
So, this question is taken from here https://gateoverflow.in/151057/langleranglethereexistinputwhoselengththanwhichhalts%24 $L=\{<M> $M is a Turing machine and there exists an input whose length is less than 100 on which M halts$\}$ I got ... may take too long before it says yes, can we be sure whether we are really reaching an answer or TM has got into infinite loop?
asked
Dec 26, 2018
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.5k
points)

53
views
decidability
theoryofcomputation
+1
vote
1
answer
17
NTA NET DEC 18 Q36
asked
Dec 25, 2018
in
Theory of Computation
by
Sanjay Sharma
Veteran
(
50.5k
points)

79
views
decidability
+1
vote
1
answer
18
NTA NET DEC 2018 Q21
asked
Dec 25, 2018
in
Theory of Computation
by
Sanjay Sharma
Veteran
(
50.5k
points)

80
views
decidability
0
votes
0
answers
19
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
asked
Dec 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

58
views
decidability
#theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
20
#decidablity
M is a TM and L(M) does not accepts 00 and 11. M is a TM and L(M) is countable . RE or NOT RE?
asked
Dec 22, 2018
in
Theory of Computation
by
Deepesh Pai
(
499
points)

48
views
theoryofcomputation
decidability
0
votes
0
answers
21
self doubt
L={ <M>  ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS } here what can we say about ‘L’?
asked
Dec 22, 2018
in
Theory of Computation
by
newdreamz a1z0
Active
(
1.6k
points)

76
views
theoryofcomputation
decidability
0
votes
0
answers
22
Rice theorem
1.{<M> M is a TM accepts any string starting with 1} 2.{<M> M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
asked
Dec 17, 2018
in
Theory of Computation
by
Learner_jai
Active
(
2.6k
points)

66
views
ricetheorem
decidability
0
votes
0
answers
23
Zeal Theory of Computation module.
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
asked
Dec 17, 2018
in
Theory of Computation
by
Ayan21
(
107
points)

54
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
24
Turing Machine lecture content stan..
A = { <M,w>  M is a TM that accepts W} what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf
asked
Dec 16, 2018
in
Theory of Computation
by
Learner_jai
Active
(
2.6k
points)

40
views
turingmachine
decidability
0
votes
1
answer
25
Ace Academy Test series
asked
Dec 15, 2018
in
Theory of Computation
by
amitqy
Active
(
1.5k
points)

85
views
decidability
0
votes
0
answers
26
ME Test Series #TOC decidability
Consider <M> be the encoding of Turing Machine as string over alphabet $\Sigma$ = {0,1}.Consider L= { <M> M is TM that halt on all input and L(M) = L` for some undecidable language L` . Then L is Decidable and Recursive Decidable and non Recursive Undecidable and Recursive Undecidable and non Recursive
asked
Dec 13, 2018
in
Theory of Computation
by
Hemanth_13
Loyal
(
6.5k
points)

82
views
theoryofcomputation
decidability
madeeasytestseries
turingmachine
0
votes
1
answer
27
Self Doubt
If L is CFL then $\bar{L}$ is Recursive. ( True/False) If L is CFL then $\bar{L}$ is RE. (True/Flase).
asked
Dec 13, 2018
in
Theory of Computation
by
kumar.dilip
Active
(
5k
points)

36
views
theoryofcomputation
decidability
0
votes
0
answers
28
Decidable
Which one is True? $1)$ A set $S$ , some of it’s elements creates injective function. Then S is decidable $2)$ A bijective function can be $NP$ Hard $3)$ A function which is Recursive Enumerable. Inverse of this function is decidable
asked
Dec 12, 2018
in
Theory of Computation
by
srestha
Veteran
(
108k
points)

62
views
theoryofcomputation
decidability
0
votes
1
answer
29
Self Doubt
L= { M⟩L(M) accepts empty string} L={⟨M⟩TM halts on empty string} Identify RE , REC , Not RE ?? Are this two languages or same I think both are same if TM halts on $\epsilon$ then L(M) accepts $\epsilon$ right ??
asked
Dec 10, 2018
in
Theory of Computation
by
jatin khachane 1
Loyal
(
6.4k
points)

35
views
theoryofcomputation
decidability
0
votes
2
answers
30
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
asked
Dec 10, 2018
in
Theory of Computation
by
gmrishikumar
Active
(
1.7k
points)

88
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
turingmachine
ricetheorem
Page:
1
2
3
4
5
6
...
11
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
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
I am not a ranker so you might not believe on my...
What is the status on appsgate website? I...
Can the ppt be made available?
47,928
questions
52,334
answers
182,380
comments
67,807
users