Recent questions tagged decidability

593 views

Kalpataru Bose asked Sep 4, 2018

0 votes

0 answers

212

Gate-overflow questions
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of them have different answers and I am not able to decide which one is correct. https://gateoverflow.in/82703/toc-turing-machine https://gateoverflow.in/98850/turing-machine

I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of the...

Swapnil Naik

288 views

Swapnil Naik asked Sep 2, 2018

1 votes

0 answers

213

Decidability
Ans. D

Ans. D

Na462

213 views

Na462 asked Sep 2, 2018

2 votes

1 answer

214

Turing Decidable

Na462

829 views

Na462 asked Sep 2, 2018

0 votes

0 answers

215

Decidability
Ans. B

Ans. B

Na462

405 views

Na462 asked Sep 2, 2018

2 votes

0 answers

216

Doubt TOC
which of the following is/are decidable? 1)for some input if an arbitrary TM makes 5 moves. 2) whether an arbitary TM halts within 5 steps 3) whether an arbitary TM prints some non blank character 4)the set of codes for TM that never make a left move. 5)an arbitrary TM halts after 100 steps 6)a TM prints a specific letter 7) a turing machine computes the product of two numbers.

which of the following is/are decidable?1)for some input if an arbitrary TM makes 5 moves.2) whether an arbitary TM halts within 5 steps3) whether an arbitary TM prints s...

Sumit Singh Chauhan

888 views

Sumit Singh Chauhan asked Aug 24, 2018

1 votes

1 answer

217

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

Choose the correct statement. A class of languages that is closed underA. Intersection and complementation has not to be closed under unionB. Union and complementation ha...

Sumit Singh Chauhan

382 views

Sumit Singh Chauhan asked Aug 15, 2018

0 votes

1 answer

218

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.

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 languag...

Sumit Singh Chauhan

271 views

Sumit Singh Chauhan asked Aug 15, 2018

2 votes

2 answers

219

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

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) Undecid...

manisha11

767 views

manisha11 asked Aug 10, 2018

0 votes

0 answers

220

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

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 ...

manisha11

300 views

manisha11 asked Aug 10, 2018

1 votes

1 answer

221

#Self doubt
Whether a given context-free language is regular is decidable or undecidable? Prove your answer!

Whether a given context-free language is regular is decidable or undecidable?Prove your answer!

himgta

432 views

himgta asked Jul 29, 2018

0 votes

0 answers

222

self doubt
is p and np problem are in syllabus in toc ???

is p and np problem are in syllabus in toc ???

vijju532

246 views

vijju532 asked Jul 26, 2018

2 votes

1 answer

223

#undecidability
why recursive enumerable languages does not satisfy the complementation property ???

why recursive enumerable languages does not satisfy the complementation property ???

vijju532

399 views

vijju532 asked Jul 24, 2018

2 votes

1 answer

224

self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??

Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??

Vegeta

646 views

Vegeta asked Jul 24, 2018

9 votes

0 answers

225

Decidability Vs Semi-Decidability Vs Undecidability Self Doubt
Please tell whether the following is Decidable, Semi-decidable or Undecidable A turing machine halts after running for exactly k steps A turing machine halts after running for atmost k steps A turing machine halts after running ... ;x" A turing machine visits a particular state "q" atleast k times on input "x"

Please tell whether the following is Decidable, Semi-decidable or UndecidableA turing machine halts after running for exactly k stepsA turing machine halts after running ...

Balaji Jegan

2.4k views

Balaji Jegan asked Jul 12, 2018

0 votes

0 answers

226

Semi-decidability 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 semi-decidable 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?

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 semi-decidable and which are Und...

Balaji Jegan

617 views

Balaji Jegan asked Jun 20, 2018

0 votes

0 answers

227

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?

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...

!KARAN

283 views

!KARAN asked Jun 17, 2018

1 votes

1 answer

228

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. ... for all even length string of infinite language etc. Now, the question is 1) is D countable? 2) is D decidable?

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...

srestha

228 views

srestha asked Jun 15, 2018

2 votes

3 answers

229

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?

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?

srestha

2.1k views

srestha asked Jun 1, 2018

1 votes

1 answer

230

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

Which of the following problems is solvable?a) Writing a universal Turing machineb) Determining if an arbitrary Turing machine is a Universal Turing Machinec) Determining...

gauravkc

6.0k views

gauravkc asked Apr 25, 2018

3 votes

2 answers

231

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

{$<M>\mid M$ is a $TM$ that doesn't accept any even number}what type of language is it?Recursively enumerableRecursiveNot recursively enumerablenone of the above

Sambit Kumar

752 views

Sambit Kumar asked Mar 15, 2018

0 votes

1 answer

232

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 ?

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 recu...

Jeevesh

431 views

Jeevesh asked Mar 4, 2018

0 votes

0 answers

233

#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 ?

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 th...

Abbas2131

313 views

Abbas2131 asked Feb 23, 2018

38 votes

3 answers

234

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 $G$ and a string $w$, whether $w \in L(G)$ Given a Turing machine ... 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

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 $...

gatecse

16.8k views

gatecse asked Feb 14, 2018

2 votes

1 answer

235

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

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...

srestha

414 views

srestha asked Jan 27, 2018

1 votes

2 answers

236

decidability
Is the following problem decidable-: 1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ? Please also provide explaination.

Is the following problem decidable-:1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ?Please also provide explaination.

Aakanchha

896 views

Aakanchha asked Jan 26, 2018

1 votes

0 answers

237

Rice's Theorem
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.

What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.

Sumaiya23

436 views

Sumaiya23 asked Jan 23, 2018

2 votes

2 answers

238

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.

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.

MIRIYALA JEEVAN KUMA

1.3k views

MIRIYALA JEEVAN KUMA asked Jan 21, 2018

6 votes

4 answers

239

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?

Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?

nikhil_cs

3.0k views

nikhil_cs asked Jan 18, 2018

3 votes

0 answers

240

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 language cannot be commutative until atleast one of them is ‘Φ’ or ‘∈’. Which of the following is correct?

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 d...

Sukhdip Singh

617 views

Sukhdip Singh asked Jan 16, 2018

Page:

« prev
1
...
3
4
5
6
7
8
9
10
11
12
13
...
16
next »

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

Materials: