Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
0
votes
0
answers
151
TOC(Undecidability)
L1 = { <M> | M halts on $\epsilon$ } L2 = { <M> | $\epsilon$ $\in$ L(M) } Which one is RE or not RE
L1 = { <M | M halts on $\epsilon$ }L2 = { <M | $\epsilon$ $\in$ L(M) }Which one is RE or not RE
jatin khachane 1
697
views
jatin khachane 1
asked
Jan 8, 2019
Theory of Computation
theory-of-computation
decidability
+
–
2
votes
0
answers
152
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 c-Undecidable and non RE d- Decidable but RE
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty}Which of the following is true?a- Decidable RECB- Undecidable and REc-Undecidable and non REd- Decidable ...
bts1jimin
578
views
bts1jimin
asked
Jan 8, 2019
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
153
UPPCL AE 2018:41
The problem of finding an integral solution of a given system of integral polynomial equations has complexity: Polynomial-time Exponential-space Undecidable Exponential-time
The problem of finding an integral solution of a given system of integral polynomial equations has complexity:Polynomial-timeExponential-spaceUndecidableExponential-time
admin
258
views
admin
asked
Jan 5, 2019
Theory of Computation
uppcl2018
theory-of-computation
decidability
+
–
0
votes
1
answer
154
UPPCL AE 2018:28
Which of the following problems are decidable? Checking whether two regular languages are equivalent Checking whether two non-deterministic finite automata accept the same language Checking whether two context free grammars generate equivalent languages Checking whether a language of a context free grammar is ... $\text{I, II, III}$ and $\text{IV}$ $\text{I}$ and $\text{II}$ only
Which of the following problems are decidable?Checking whether two regular languages are equivalentChecking whether two non-deterministic finite automata accept the same ...
admin
221
views
admin
asked
Jan 5, 2019
Theory of Computation
uppcl2018
theory-of-computation
decidability
+
–
1
votes
1
answer
155
MadeEasy Test Series: Theory Of Computation - Decidability
Among II and III. Which one is decidable ? Please explain in detail.
Among II and III. Which one is decidable ? Please explain in detail.
Shamim Ahmed
425
views
Shamim Ahmed
asked
Jan 4, 2019
Theory of Computation
made-easy-test-series
theory-of-computation
decidability
+
–
2
votes
0
answers
156
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 non-trivial 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?
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 non-trivial property ...
Ayush Upadhyaya
661
views
Ayush Upadhyaya
asked
Jan 3, 2019
Theory of Computation
decidability
theory-of-computation
+
–
1
votes
2
answers
157
UGC NET CSE | December 2018 | Part 2 | Question: 37
Consider the following problems : Whether a finite state automaton halts on all inputs? Whether a given context free language is regular? Whether a Turing machine computes the product of two numbers? Which one of the following is ... ii and iii are undecidable problems Only i and ii are undecidable problems i, ii and iii are undecidable problems
Consider the following problems :Whether a finite state automaton halts on all inputs?Whether a given context free language is regular?Whether a Turing machine computes t...
Arjun
1.7k
views
Arjun
asked
Jan 2, 2019
Theory of Computation
ugcnetcse-dec2018-paper2
decidability
theory-of-computation
+
–
0
votes
0
answers
158
TOC Doubt
CFG G=(N,Σ,P,S) and a string x∈Σ∗, does x∈L(G)} ? Is it Decidable?
CFG G=(N,Σ,P,S) and a string x∈Σ∗, does x∈L(G)} ?Is it Decidable?
Shamim Ahmed
437
views
Shamim Ahmed
asked
Jan 2, 2019
Theory of Computation
theory-of-computation
decidability
+
–
1
votes
1
answer
159
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.
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.
Ayan21
495
views
Ayan21
asked
Dec 30, 2018
Theory of Computation
decidability
theory-of-computation
context-free-language
recursive-and-recursively-enumerable-languages
+
–
3
votes
1
answer
160
GATE Overflow | Mock GATE | Test 1 | Question: 24
Let a problem $P_1$ is reducible to another problem $P_2$. Identify the incorrect statement. (i) If $P_2$ is decidable then $P_1$ must be decidable (ii) If $P_2$ is un-decidable then $P_1$ may or mayn't be undecidable (iii) If $P_2$ is decidable then ... of $P_1$ is independent of $P_2$ (i) and (ii) (ii) and (iv) (ii) and (iii) (iii) and (iv)
Let a problem $P_1$ is reducible to another problem $P_2$. Identify the incorrect statement.(i) If $P_2$ is decidable then $P_1$ must be decidable(ii) If $P_2$ is un-deci...
Ruturaj Mohanty
581
views
Ruturaj Mohanty
asked
Dec 27, 2018
Theory of Computation
go-mockgate-1
decidability
theory-of-computation
reduction
+
–
0
votes
1
answer
161
self doubt
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
mrinmoyh
288
views
mrinmoyh
asked
Dec 27, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
162
Decidability
So, this question is taken from here https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%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?
So, this question is taken from here https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%24 $L=\{<M>| $M is a Turing machine and ...
Ayush Upadhyaya
329
views
Ayush Upadhyaya
asked
Dec 26, 2018
Theory of Computation
decidability
theory-of-computation
+
–
0
votes
0
answers
163
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
please someone explain what are these problems and how to solve these problems for every language with proper explanation?MEMBERSHIP PROBLEMEMPTINESS PROBLEMCOMPLETENESS ...
Rahul_Rathod_
941
views
Rahul_Rathod_
asked
Dec 24, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
164
#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?
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?
Deepesh Pai
441
views
Deepesh Pai
asked
Dec 22, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
165
self doubt
L={ <M> | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS } here what can we say about ‘L’?
L={ <M | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS }here what can we say about ‘L’?
newdreamz a1-z0
448
views
newdreamz a1-z0
asked
Dec 22, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
166
Zeal Test Series 2019: Theory of Computation - Decidability
according to me 1) and 4) are right 2 and 3) i am not getting
according to me 1) and 4) are right 2 and 3) i am not getting
Prince Sindhiya
275
views
Prince Sindhiya
asked
Dec 21, 2018
Theory of Computation
zeal
theory-of-computation
decidability
zeal2019
+
–
0
votes
0
answers
167
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 .
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 = { s...
Learner_jai
589
views
Learner_jai
asked
Dec 17, 2018
Theory of Computation
rice-theorem
decidability
+
–
1
votes
1
answer
168
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.
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.
Ayan21
586
views
Ayan21
asked
Dec 17, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
1
votes
1
answer
169
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
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/c...
Learner_jai
296
views
Learner_jai
asked
Dec 16, 2018
Theory of Computation
turing-machine
decidability
+
–
0
votes
1
answer
170
Ace Academy Test series
amitqy
376
views
amitqy
asked
Dec 15, 2018
Theory of Computation
decidability
+
–
3
votes
3
answers
171
MadeEasy Subject Test 2019: Theory Of Computation - 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
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 undecidab...
Hemanth_13
3.4k
views
Hemanth_13
asked
Dec 13, 2018
Theory of Computation
made-easy-test-series
theory-of-computation
decidability
turing-machine
+
–
2
votes
1
answer
172
Self Doubt
If L is CFL then $\bar{L}$ is Recursive. ( True/False) If L is CFL then $\bar{L}$ is RE. (True/Flase).
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).
kumar.dilip
459
views
kumar.dilip
asked
Dec 13, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
173
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
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...
srestha
384
views
srestha
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
1
answer
174
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 ??
L= { M⟩|L(M) accepts empty string} L={⟨M⟩|TM halts on empty string} Identify RE , REC , Not RE ??Are this two languages or sameI think both are same if TM halts on...
jatin khachane 1
384
views
jatin khachane 1
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
decidability
+
–
1
votes
3
answers
175
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
gmrishikumar
1.7k
views
gmrishikumar
asked
Dec 10, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
rice-theorem
+
–
0
votes
0
answers
176
Self doubt
which is/are TRUE: 1)All recursive lang are decidable problems? 2)All decidable problems are recursive language? - is both of them are true? any proof please?
which is/are TRUE:1)All recursive lang are decidable problems?2)All decidable problems are recursive language?- is both of them are true? any proof please?
pps121
195
views
pps121
asked
Dec 8, 2018
Theory of Computation
decidability
+
–
1
votes
0
answers
177
Undecidability with PCP
Where can we apply PCP to check, if the grammar is undecidable? Some examples of such grammars Ambiguous grammar Any other example and how they solved with PCP?
Where can we apply PCP to check, if the grammar is undecidable?Some examples of such grammars Ambiguous grammarAny other example and how they solved with PCP?
srestha
367
views
srestha
asked
Dec 6, 2018
Theory of Computation
theory-of-computation
decidability
+
–
2
votes
0
answers
178
TOC-Undecidability
Here is my analysis. P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within ... decide P3. Hence, P3 is decidable.->REC. So, I think here answer must be 1. Please let me know what's right.
Here is my analysis.P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes f...
Ayush Upadhyaya
926
views
Ayush Upadhyaya
asked
Nov 23, 2018
Theory of Computation
theory-of-computation
decidability
rice-theorem
+
–
0
votes
0
answers
179
Decidability Doubt
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$ ... because $\exists$ infinite number of TM's which accept $\Sigma^*$. Now $L(M)$ is not even RE. If that then how $L_1$ is RE. Please explain both.
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$$L_2 = \{ \text{<M>} | \ \text{M is a TM,...
Mk Utkarsh
410
views
Mk Utkarsh
asked
Nov 23, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
0
votes
0
answers
180
Self doubt decidability
$\text{L}_1 = \{\text{<M>}|\text{M is a TM and L(M) is infinite} \}$ Not RE $\text{L}_2 = \{ \text{<M>} | \text{M is a TM and L(M) is countable} \}$ and $\text{L}_3 = \{ \text{<M>} | \text{M is a TM and L(M) is uncountable}\}$ both are Recursive how?
$\text{L}_1 = \{\text{<M>}|\text{M is a TM and L(M) is infinite} \}$Not RE$\text{L}_2 = \{ \text{<M>} | \text{M is a TM and L(M) is countable} \}$and $\text{L}_3 = \{ \t...
Mk Utkarsh
401
views
Mk Utkarsh
asked
Nov 23, 2018
Theory of Computation
decidability
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
16
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register