Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
2
votes
2
answers
241
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 ............"
yogi_p
asked
in
Theory of Computation
Jan 13, 2018
by
yogi_p
912
views
theory-of-computation
decidability
rice-theorem
4
votes
0
answers
242
MadeEasy Test Series 2018: Theory of Computation - Turing Machine
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
Bhavya Bhatia
asked
in
Theory of Computation
Jan 11, 2018
by
Bhavya Bhatia
2.4k
views
theory-of-computation
turing-machines
decidability
madeeasy-testseries-2018
3
votes
0
answers
243
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
Nymeria
asked
in
Theory of Computation
Jan 10, 2018
by
Nymeria
887
views
decidability
context-free-language
turing-machine
reduction
2
votes
0
answers
244
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 ??
Venkat Sai
asked
in
Theory of Computation
Jan 9, 2018
by
Venkat Sai
864
views
theory-of-computation
decidability
rice-theorem
2
votes
1
answer
245
Test Series
Explain please. Answer given is D
Anmol_Binani
asked
in
Theory of Computation
Jan 2, 2018
by
Anmol_Binani
665
views
theory-of-computation
decidability
1
vote
1
answer
246
not partially decidable
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?
Mk Utkarsh
asked
in
Theory of Computation
Jan 2, 2018
by
Mk Utkarsh
904
views
theory-of-computation
decidability
2
votes
4
answers
247
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is a) Decidable b) Semi decidable c) not even semi-decidable
Abhishek Kumar Singh
asked
in
Theory of Computation
Dec 30, 2017
by
Abhishek Kumar Singh
1.2k
views
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
2
answers
248
Theory_of_computation
Q-1) What are the things that are not decidable about DCFL or DCFG? 2)How complexity theory is related to formal langauages ,I know that pure complexity lies in decidable region but question like this confuses me : 3) Apart from this this question : ... how we calculate the quotient and moreover question asks to draw the dfa for the same language,how to work with quotient .?
saxena0612
asked
in
Theory of Computation
Dec 27, 2017
by
saxena0612
730
views
theory-of-computation
decidability
0
votes
0
answers
249
Turing Machine
A. L is undecidable B. L is decidable C. L is regular. D. None of these. Please explain in detail.
Shubham Kumar Gupta
asked
in
Theory of Computation
Dec 23, 2017
by
Shubham Kumar Gupta
590
views
turing-machine
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
2
votes
2
answers
250
Decidability
Equality of two DPDA is decidable or undecidable ?
dragonball
asked
in
Theory of Computation
Dec 20, 2017
by
dragonball
1.7k
views
theory-of-computation
decidability
0
votes
1
answer
251
Decidability
L= {<G> | G is CFG and G is NOT ambiguous} . L is TM recognizable or not even TM recognizable?
Soumya29
asked
in
Theory of Computation
Dec 16, 2017
by
Soumya29
1.1k
views
decidability
theory-of-computation
1
vote
1
answer
252
Decidability
Need Explaination : _________________________________________________________________ " Whether L(G) is a regular language? "-It is undecidable 1)question is why is it undecidable? ___________________________________________________________________ " Whether L(G) is a CFL? (trivial) "- it is decidable 2)question is why is it decidable?
srestha
asked
in
Theory of Computation
Dec 16, 2017
by
srestha
577
views
decidability
theory-of-computation
0
votes
0
answers
253
Doubt in Rice's Theorem
I have a doubt while understanding step 2 in proof of Rice's Theorem- According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is non ... problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
Durgesh Singh
asked
in
Theory of Computation
Dec 14, 2017
by
Durgesh Singh
472
views
rice-theorem
decidability
theory-of-computation
self-doubt
turing-machine
0
votes
0
answers
254
Ace Test Series: Theory Of Computation - Decidability
saxena0612
asked
in
Theory of Computation
Dec 7, 2017
by
saxena0612
305
views
complexity-theory
decidability
ace-test-series
theory-of-computation
0
votes
0
answers
255
Rice theorem problem
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps? Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable. @arjun sir ,@bikram sir or @others
hem chandra joshi
asked
in
Theory of Computation
Dec 1, 2017
by
hem chandra joshi
1.1k
views
rice-theorem
theory-of-computation
decidability
theorem
rice
4
votes
1
answer
256
MadeEasy Subject Test: Theory of Computation - Decidability
1) L is undecidable 2) L is decidable 3) L is regular 4) none Answer given: 1) undecidable My solution: Since L(M) is reducible to a CFL language and since all CFL are recursive that means language accepted by M is ... halts on all inputs so this language will too and answer should be decidable. How to approach this type of question ?
♥_Less
asked
in
Theory of Computation
Nov 30, 2017
by
♥_Less
733
views
made-easy-test-series
theory-of-computation
decidability
1
vote
2
answers
257
Self doubt in TOC
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
Parshu gate
asked
in
Theory of Computation
Nov 29, 2017
by
Parshu gate
882
views
theory-of-computation
regular-language
decidability
context-free-language
turing-machine
1
vote
1
answer
258
Self doubt in terminologies and turing machine
1) I know that turing decidable means recursive language. But does is also means its decidable? So basically i want to know if REC imples decidability and RE implies undecidability or not. I got confused with word decidable in " ... same expressive power why can't we use DTM in NP decision problems? Thanks for being patient and reading doubt.
♥_Less
asked
in
Theory of Computation
Nov 29, 2017
by
♥_Less
1.1k
views
theory-of-computation
turing-machine
decidability
self-doubt
p-np-npc-nph
3
votes
3
answers
259
Self doubt in decidability in TOC
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?
Parshu gate
asked
in
Theory of Computation
Nov 29, 2017
by
Parshu gate
643
views
theory-of-computation
regular-language
decidability
turing-machine
2
votes
1
answer
260
Decidability
Which of the following decision problem is undecidable? I)Given a CFG $G=\left ( N,\Sigma ,P,S \right )$ and a string $x\epsilon \Sigma ^{*}$, does $x\epsilon L\left ( G \right )$? II) Given CFG $G_{1},G_{2}$, Is $L\left ( G_{1} \right )=L\left (G_{2} \right )$?
srestha
asked
in
Theory of Computation
Nov 28, 2017
by
srestha
845
views
decidability
theory-of-computation
0
votes
1
answer
261
The Infiniteness Problem
what is the Infiniteness Problem?
Mk Utkarsh
asked
in
Theory of Computation
Nov 27, 2017
by
Mk Utkarsh
853
views
theory-of-computation
algorithms
decidability
2
votes
1
answer
262
Problem
What is Equality Problem in Theory of computation?
Nikhil Patil
asked
in
Theory of Computation
Nov 21, 2017
by
Nikhil Patil
272
views
theory-of-computation
decidability
context-free-language
identify-class-language
4
votes
0
answers
263
Proof of Decidability and Closure properties of various language ?
Hi Guys, If someone can provide proof or some kind of intuition for following properties then it will be great help. Because many problem could be solved via these two tables. https://gatecse.in/grammar-decidable-and-undecidable-problems/ https://gatecse.in/closure-property-of-language-families/ PS: Mainly for CFL, CSL, REC and RE.
Chhotu
asked
in
Theory of Computation
Nov 19, 2017
by
Chhotu
546
views
theory-of-computation
closure-property
decidability
4
votes
1
answer
264
TOC CONCEPTUAL
Which are the correct arguments? 1) if A is a subset of B, and B is decidable, than A is guaranteed to be decidable. 2) If L is Turing-decidable and L' is regular. Then L ∩ L' is regular. 3) The language L = {<D> | D is a DFA and there exists a TM M such that ... If L1 reduces to L2 and L2 is undecidable, then L1 is undecidable. (A) 1, 2, 3 (B) 3, 4 (C) 1, 3 (D) 2, 3
Parshu gate
asked
in
Theory of Computation
Nov 11, 2017
by
Parshu gate
802
views
turing-machine
regular-language
theory-of-computation
decidability
3
votes
0
answers
265
Undecidability
L = {<M> | M is a TM and L(M) is infinite }..How to prove it as not RE..Here L(Tyes) = Sigma* is not subset of L(Tno) = Phi..So Rice Theorem's 2nd part is not applicable.. Can anyone please explain it ?
ankitgupta.1729
asked
in
Theory of Computation
Nov 11, 2017
by
ankitgupta.1729
481
views
decidability
theory-of-computation
3
votes
1
answer
266
Undecidability
L = { <M> | M is a TM and |L(M)| <= 3 }. Is it Recursively Enumerable or not ?
ankitgupta.1729
asked
in
Theory of Computation
Nov 11, 2017
by
ankitgupta.1729
1.1k
views
decidability
theory-of-computation
2
votes
1
answer
267
UGC NET CSE | November 2017 | Part 3 | Question: 22
Which of the following problems is undecidable? To determine if two finite automata are equivalent Membership problem for context free grammar Finiteness problem for finite automata Ambiguity problem for context free grammar
Arjun
asked
in
Theory of Computation
Nov 5, 2017
by
Arjun
1.2k
views
ugcnetcse-nov2017-paper3
theory-of-computation
decidability
1
vote
1
answer
268
#TOC Turing Machine Question
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine. I know, other way is correct i.e for every DTM there exist a NDTM, but is above TRUE/FALSE. Thank you!
iarnav
asked
in
Theory of Computation
Nov 1, 2017
by
iarnav
907
views
turing-machine
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
self-doubt
1
vote
2
answers
269
Decidability Question
a) language accepted by a CFG(Context free grammar) is nonempty. is it D or UD?
iarnav
asked
in
Theory of Computation
Oct 30, 2017
by
iarnav
2.2k
views
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
context-free-language
0
votes
1
answer
270
Turing Machine Question
The set of turning machines which halt on empty input forms a recursively enumerable set?! True or False. Please also state your reason/explanation. AFAIK - TM accept Epsilon if it sees a Blank and goes to accepting state. Thank you!
iarnav
asked
in
Theory of Computation
Oct 30, 2017
by
iarnav
686
views
turing-machine
decidability
recursive-and-recursively-enumerable-languages
Page:
« prev
1
...
4
5
6
7
8
9
10
11
12
13
14
...
16
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged decidability
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...