Register

Materials:

Recent questions tagged decidability

57 57 votes
7 answers 7 answers
28.4k
28.4k views
GATE CSE 2018 | Question: 36
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 $...
User Avatar
2 2 votes
1 1 answer
975
975 views
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 decidableb) L is undecidablec)L is partially decida...
User Avatar
1 1 vote
2 2 answers
1.6k
1.6k views
decidability
Is the following problem decidable-:1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ?Please also provide explaination.
User Avatar
1 1 vote
0 0 answers
702
702 views
Rice's Theorem
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
User Avatar
2 2 votes
2 2 answers
2.3k
2.3k views
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.
User Avatar
6 6 votes
4 4 answers
4.0k
4.0k views
Intersection of two Recursive languages are of same type or not. Is it decidable or undecidable?
Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?
User Avatar
3 3 votes
0 0 answers
1.2k
1.2k views
MadeEasy Test Series 2018: Theory of Computation - Decidability
Consider the following statements:S1 : Let L be language, reversal of language L cannot contain any string present in ‘L’ except ‘∈’.S2 : Concatenation of two different l...
User Avatar
2 2 votes
2 answers 2 answers
2.1k
2.1k views
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 1L =...
User Avatar
4 4 votes
0 0 answers
4.0k
4.0k views
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) Undec...
User Avatar
3 3 votes
0 0 answers
1.7k
1.7k views
Decidability
a) L is decidableb) L is undecidablec) L is regulard) None of these
User Avatar
2 2 votes
0 0 answers
1.8k
1.8k views
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 Tur...
User Avatar
2 2 votes
1 1 answer
1.3k
1.3k views
Test Series
Explain please. Answer given is D
User Avatar
1 1 vote
1 1 answer
1.5k
1.5k views
not partially decidable
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?
User Avatar
2 2 votes
4 answers 4 answers
3.5k
3.5k views
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ isa) Decidable b) Semi decidable c) not even semi-decidable
User Avatar
0 0 votes
2 answers 2 answers
1.4k
1.4k views
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...
User Avatar
0 0 votes
0 0 answers
1.0k
1.0k views
Turing Machine
A. L is undecidableB. L is decidableC. L is regular.D. None of these.Please explain in detail.
User Avatar
2 2 votes
2 2 answers
2.3k
2.3k views
Decidability
Equality of two DPDA is decidable or undecidable ?
User Avatar
0 0 votes
1 1 answer
2.1k
2.1k views
Decidability
L= {<G | G is CFG and G is NOT ambiguous} .L is TM recognizable or not even TM recognizable?
User Avatar
1 1 vote
1 1 answer
1.1k
1.1k views
Decidability
Need Explaination :_________________________________________________________________" Whether L(G) is a regular language? "-It is undecidable1)question is why is it undec...
User Avatar
0 0 votes
0 0 answers
834
834 views
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 wro...
User Avatar
0 0 votes
0 0 answers
2.3k
2.3k views
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 o...
User Avatar
4 4 votes
1 1 answer
1.5k
1.5k views
MadeEasy Subject Test: Theory of Computation - Decidability
1) L is undecidable2) L is decidable3) L is regular4) none Answer given: 1) undecidableMy solution: Since L(M) is reducible to a CFL language and since all CFL are recurs...
User Avatar
1 1 vote
2 2 answers
1.8k
1.8k views
Self doubt in TOC
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
User Avatar
1 1 vote
1 answers 1 answer
1.7k
1.7k views
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 unde...
User Avatar
3 3 votes
3 answers 3 answers
1.3k
1.3k views
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?
User Avatar
2 2 votes
1 1 answer
1.4k
1.4k views
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 \...
User Avatar
0 0 votes
1 1 answer
1.4k
1.4k views
The Infiniteness Problem
what is the Infiniteness Problem?
User Avatar
2 2 votes
1 1 answer
575
575 views
Problem
What is Equality Problem in Theory of computation?
User Avatar
4 4 votes
0 0 answers
757
757 views
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 tab...
User Avatar
Page: