Recent questions tagged decidability

Test by Bikram | Theory of Computation | Test 2 | Question: 17
Match the following statements with True (T) / False (F) : $S1: \ CFG = \{ <G> \mid \text{ G is a CFG and } L (G) = \Sigma ^* \} \text{ is undecidable}$ ... , S2 - F, S3 - T , S4 - T S2 - T, S3 - F, S1 - T , S4 - T S1 - T, S2 - F, S3 - T , S4 - F

Match the following statements with True (T) / False (F) :$S1: \ CFG = \{ <G \mid \text{ G is a CFG and } L (G) = \Sigma ^* \} \text{ is undecidable}$$S2: \ A = \{ <G \mi...

Bikram

435 views

Bikram asked Aug 12, 2017

0 votes

1 answer

302

Test by Bikram | Theory of Computation | Test 2 | Question: 13
Which of the following statements are NOT true? Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$. Given two arbitrary context-free grammars $G1$ and $G2$ ... a particular non-terminal "X" in G is reachable. I,IV and II II and IV I and IV I,II and III

Which of the following statements are NOT true?Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$.Given two arbitrary context-free gram...

Bikram

429 views

Bikram asked Aug 12, 2017

1 votes

0 answers

303

Turing Machines Deciadability
L ={ T | e(T) belongs to L(T) } , e(T) is the code for turing machine? The answer given is RE but not REC ,but cant we apply Rice theorem as follow- Tyes={Any machine accepting its code} Tno={Machine accepting code of Tyes + a } // ... applied to T,then members will say say and for Non members it may or may not halt.But where am i wrong in Rice's theorem proof?

L ={ T | e(T) belongs to L(T) } , e(T) is the code for turing machine?The answer given is RE but not REC ,but cant we apply Rice theorem as follow-Tyes={Any machine accep...

rahul sharma 5

496 views

rahul sharma 5 asked Aug 8, 2017

3 votes

2 answers

304

TOC Turing machines Decidability
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? L={⟨M⟩∣ M halts on all palindromes}. How can i use Rice's theorem here? Tyes={All palidroms} Tno={Signma*}.Will that work here? M halts on all palindromes means M halts on only palindromes ?

Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?L={⟨M⟩∣ M halts on all palindromes}.How can i...

rahul sharma 5

994 views

rahul sharma 5 asked Aug 7, 2017

2 votes

2 answers

305

Turing machines decidability
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? {⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M1)∖L(M2)}.

Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?{⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M...

rahul sharma 5

661 views

rahul sharma 5 asked Aug 7, 2017

2 votes

0 answers

306

TOC:- Turing Machines Decidiability
Please help in classifying above languages

Please help in classifying above languages

rahul sharma 5

431 views

rahul sharma 5 asked Aug 5, 2017

1 votes

1 answer

307

Turing Machine Rice's Theorem
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What ... am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.

L = {M|M is a TM that accepts all even numbers}For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i c...

rahul sharma 5

1.3k views

rahul sharma 5 asked Aug 5, 2017

3 votes

1 answer

308

TOC Semi decidable problems
As per Rice's theorem if the problem is undecidable then it can be RE but Not REC or Not RE. So basically if something is not decidable,then it can be either RE but not REC or Not RE. But i have also read that RE consists ... do we consider semi decidable as undecidable also?Can i say every undecidable is Not RE?or the other way every semidecidable is undecidable?

As per Rice's theorem if the problem is undecidable then it can be RE but Not REC or Not RE. So basically if something is not decidable,then it can be either RE but not R...

rahul sharma 5

543 views

rahul sharma 5 asked Aug 3, 2017

3 votes

1 answer

309

TOC Semi Decidable
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?

Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?

rahul sharma 5

2.0k views

rahul sharma 5 asked Aug 1, 2017

1 votes

0 answers

310

Self doubt
Please provide suggestions for following points- Can Type-0 grammar be written for a Regular Language which is not Type 1,2 or 3. Can any Type 0 grammar be checked if it can be reduced to Type 1,2,3 grammar. how to check if a Type 0 grammar is decidable /undecidable How to design a turing machine by looking at Type 0 grammar

Please provide suggestions for following points-Can Type-0 grammar be written for a Regular Language which is not Type 1,2 or 3.Can any Type 0 grammar be checked if it ca...

Durgesh Singh

281 views

Durgesh Singh asked Aug 1, 2017

3 votes

1 answer

311

Turing Decidable Languages
Are Turing decidable languages are closed under Complementation, Reversal, Homomorphism, Inverse Homomorphism and Substitution?

Are Turing decidable languages are closed under Complementation, Reversal, Homomorphism, Inverse Homomorphism and Substitution?

Utkarsh Anand

1.4k views

Utkarsh Anand asked Jul 31, 2017

3 votes

3 answers

312

Why L = { w x w ∣ w , x ∈ ( a + b ) + } is not regular?
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong

We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong

Durgesh Singh

5.5k views

Durgesh Singh asked Jul 25, 2017

2 votes

0 answers

313

Rice theorem Example from (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)
L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???

L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???

akb1115

774 views

akb1115 asked Jul 18, 2017

1 votes

1 answer

314

Proof of whether a TM accepts epsilon is semi decidable
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?

From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?

Xylene

1.1k views

Xylene asked Jul 15, 2017

4 votes

3 answers

315

CFL decidability
Problem :- intersection of 2 CFL's is CFL. Is this decidable ?

Problem :- intersection of 2 CFL's is CFL. Is this decidable ?

Xylene

1.6k views

Xylene asked Jul 14, 2017

0 votes

0 answers

316

http://www.cs.rice.edu/~nakhleh/COMP481/
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks

Can anybody please explain this reduction and rice theorem.http://www.cs.rice.edu/~nakhleh/COMP481/Thanks

Arpit Dhuriya

411 views

Arpit Dhuriya asked May 24, 2017

2 votes

0 answers

317

Test by Bikram | Mock GATE | Test 4 | Question: 35
Let $DM$ be a single-tape, Deterministic Turing machine with tape alphabet $\left \{ blank,0,1 \right \}$, and let $C_i$ denote the (possibly infinite) computation of $DM$ starting with a blank tape. The input to each problem below is ... $k$ distinct tape squares during the computation $C_i.$ III only I and III only II and III only I, II, and III

Let $DM$ be a single-tape, Deterministic Turing machine with tape alphabet $\left \{ blank,0,1 \right \}$, and let $C_i$ denote the (possibly infinite) computation of $DM...

Bikram

490 views

Bikram asked May 14, 2017

0 votes

0 answers

318

TOC TM

nitish

291 views

nitish asked May 4, 2017

0 votes

0 answers

319

theory of computation
L = { <M> / M is a Turing machine and M accepts a regular language }. This Language L is recursively enumerable but not recursive. ...right ??

L = { <M / M is a Turing machine and M accepts a regular language }.This Language L is recursively enumerable but not recursive. ...right ??

vignesh

317 views

vignesh asked Apr 21, 2017

0 votes

1 answer

320

theory of computation
L = { <M,w> / M is a TM,w is a string and M on simulating w,the Read/write head of M moves 100 steps away from the left most symbol of input }.Assume initially the Read/write head is in left-most symbol of input. MY ANSWER : This language is Recursively enumerable but not recursive ...right ???

L = { <M,w / M is a TM,w is a string and M on simulating w,the Read/write head of M moves 100 steps away from the left most symbol of input }.Assume initially the Read/wr...

vignesh

409 views

vignesh asked Apr 21, 2017

0 votes

1 answer

321

theory of computation
This language, L = { <M,w> / M is a TM,w is a string and M does not halt on string w } is not recursively enumerable ...right ???

This language,L = { <M,w / M is a TM,w is a string and M does not halt on string w }is not recursively enumerable ...right ???

vignesh

351 views

vignesh asked Apr 21, 2017

2 votes

2 answers

322

theory of computation
Which of the following languages below are NOT recursively enumerable ? L1 = {<M> / M is a TM that accepts all even numbers }. L2 = {<M> / M does not accept all even numbers } L3 = {<M> / M rejects all even numbers } A) Only L1 B) Only L1 and L2 C) Only L1 and L3 D) All of L1,L2 and L3

Which of the following languages below are NOT recursively enumerable ?L1 = {<M / M is a TM that accepts all even numbers }.L2 = {<M / M does not accept all even numbers ...

vignesh

1.1k views

vignesh asked Apr 21, 2017

1 votes

4 answers

323

Is this decidable or undecidable
A = { (M, w) | M is a TM that on input w, tries to move its head past the left end of the input } B = { (M, w) | M is a TM that on input w, moves its head left at least once, at some point} how to decide that a problem is decidable or undecidable , recognisable or unrecognisable ??

A = { (M, w) | M is a TM that on input w, tries to move its head past the left end of the input }B = { (M, w) | M is a TM that on input w, moves its head left at least on...

student2018

1.9k views

student2018 asked Apr 16, 2017

2 votes

2 answers

324

Undecidability means recognizable or unrecognizable
If a problem is undecidable then can we say the problem is either recognizable or unrecognizable

If a problem is undecidable then can we say the problem is either recognizable or unrecognizable

student2018

1.6k views

student2018 asked Apr 16, 2017

0 votes

0 answers

325

Shai Simonson Lectures on TOC
In the "Halting Problem" lecture, the prof. introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove that the halting problem is undecidable. There he asked to change the algorithm ... . It would be great if somebody can shed some light on it. Thanks! https://www.youtube.com/watch?v=e9zzY7uqT8g

In the "Halting Problem" lecture, the prof. introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove tha...

GautamDas

696 views

GautamDas asked Apr 9, 2017

33 votes

3 answers

326

GATE CSE 2017 Set 2 | Question: 41
Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted by a Turing machine $M$. Which of the following decision problems are undecidable? Given a ... string $w$, is $w \in L(M)$? I and IV only II and III only II, III and IV only III and IV only

Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted ...

Madhav

8.6k views

Madhav asked Feb 14, 2017

86 votes

4 answers

327

GATE CSE 2017 Set 1 | Question: 39
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an ... $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.

Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if th...

Arjun

18.4k views

Arjun asked Feb 14, 2017

1 votes

2 answers

328

decidability
is intersection of two context sensitive decidable?? I think since they are closed under intersection, it must be decidable. please answer

is intersection of two context sensitive decidable??I think since they are closed under intersection, it must be decidable.please answer

sushmita

1.8k views

sushmita asked Feb 10, 2017

2 votes

1 answer

329

Decidability
Ambiguity of DCFL and CFL is decidable or not??

Ambiguity of DCFL and CFL is decidable or not??

Rahul Jain25

1.9k views

Rahul Jain25 asked Feb 7, 2017

0 votes

1 answer

330

Decidablity+DCFL
I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not??? II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducible to L2 and L1 is non-RE then L2 is also non-RE??

I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not???II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducibl...

Rahul Jain25

828 views

Rahul Jain25 asked Feb 7, 2017

Page:

« prev
1
...
6
7
8
9
10
11
12
13
14
15
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: