Recent questions tagged decidability

Rice's Theorem
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. ... then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?

Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of statesSol: This is a t...

Salazar

756 views

Salazar asked Oct 28, 2017

0 votes

1 answer

272

True/False
Let A(x) and B(x) be any two first order formulas that contains the free variable x(plus other non free variables). The sentence A(x) is decidable is an abbreviation for "is there an algorithm which states whether, given a value of x, A(x) is true or false." ... is not decidable. 8) If A(x) is not decidable and B(x) is not decidable, then ∀x (A(x) ∧∀yB(y)) is not decidable.

Let A(x) and B(x) be any two first order formulas that contains the free variable x(plus other non free variables). The sentence “A(x) is decidable” is an abbreviatio...

Rupendra Choudhary

628 views

Rupendra Choudhary asked Oct 27, 2017

3 votes

1 answer

273

Random
Which of the following is/are undecidable? G is a CFG. Is L(G)=ϕ? L is a CFL. Does it produce an empty set?

Which of the following is/are undecidable?G is a CFG. Is L(G)=ϕ?L is a CFL. Does it produce an empty set?

Warlock lord

411 views

Warlock lord asked Oct 23, 2017

3 votes

0 answers

274

$L= { <G>$ is a CFG & not ambiguous $}$ RE or not?
$L= { <G>$ is a CFG & not ambiguous $}$ RE or not? We can have 2 TMs where $T_{yes}\subset T_{no}$ just by adding additional ambiguous productions to an existing non ambigous CFG. So it seems to me it is not RE, but given answer is RE. Where I am wrong?

$L= { <G>$ is a CFG & not ambiguous $}$ RE or not? We can have 2 TMs where $T_{yes}\subset T_{no}$ just by adding additional ambiguous productions to an existing non ambi...

Aghori

371 views

Aghori asked Oct 22, 2017

2 votes

2 answers

275

Some Questions on Decidabilty
1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to ∅? 2) Is it decidable whether a given Turing machine accepts all strings? That is, is L(M) = A*? 3) Is it decidable whether a given ... don't know. Please tell. 2) Is it Completeness Problem? If yes, then its UD. 3) Finiteness Problem and it's UD 4) UD

1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to ∅? 2) Is it decidable whether a given Turing machine accepts...

iarnav

1.0k views

iarnav asked Oct 22, 2017

2 votes

0 answers

276

Decidabilty Question
We know given a TM (M) accepts an null string ϵ is an UD problem. Hence, L(M) will never be Recursive, but is it R.E? I mean, TM (M) can accept epsilon when it can go to an accept state on "B" on input tape. So, does it make it Semi-decidable and hence R.E? Thank you! Note/Credits: Blue line is copied from Arjun Sir's answer. Source - here

We know given a TM (M) accepts an null string ϵ is an UD problem.Hence, L(M) will never be Recursive, but is it R.E? I mean, TM (M) can accept epsilon when it can go to ...

iarnav

308 views

iarnav asked Oct 22, 2017

1 votes

0 answers

277

Doubt regarding Turing Machine
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ? Well, if T.M can't accept ε then why we are giving T.M the input ε ? Thank you!

I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ?Well, if T.M can't accept ε then why we are giving T.M the input ε ?Th...

iarnav

709 views

iarnav asked Oct 17, 2017

7 votes

0 answers

278

Decidablity problem.
Is L(G) subset of L(R) decidable ? Where G is CFG and R is regular grammar. Problem can be reduced to checking if L(G) $\cap$ ( L(R))' = phi. Now L(R)' is regular, so it also CFL and determining whether L(G1) $\cap$ L(G2) = phi is known to be undecidable where L(G1) and L(G2) are CFL's . So above problem should also be undecidable. Where am I going wrong ?

Is L(G) subset of L(R) decidable ? Where G is CFG and R is regular grammar.Problem can be reduced to checking if L(G) $\cap$ ( L(R))' = phi.Now L(R)' is regular, so it al...

Xylene

1.8k views

Xylene asked Oct 14, 2017

4 votes

1 answer

279

Turing Machine Decidability Question
L1= {⟨M⟩| M is a TM and |L(M)| = 5 }. we know about at least and at most case, but someone explain equal to case. Furthermore, I'll complie more questions in same thread only. L2= {⟨M⟩| M is a TM and M does not accept all even numbers}. L3 = {⟨M⟩| M is a TM and M reject all even numbers}.

L1= {⟨M⟩| M is a TM and |L(M)| = 5 }. we know about at least and at most case, but someone explain equal to case.Furthermore, I'll complie more questions in same thre...

iarnav

1.8k views

iarnav asked Oct 14, 2017

1 votes

0 answers

280

gatequestions
How to solve turing machine decidable/undecidable questions ? Do I need to mug them up ?

How to solve turing machine decidable/undecidable questions ? Do I need to mug them up ?

♥_Less

334 views

♥_Less asked Oct 6, 2017

6 votes

1 answer

281

Halting Problem
What is state entry problem? How Halting Problem can decide is it decidable or undecidable?

What is state entry problem? How Halting Problem can decide is it decidable or undecidable?

srestha

3.5k views

srestha asked Sep 19, 2017

2 votes

1 answer

282

Decidability
1. {<M,w>| M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')} 2. {<M>| M is a TM, and M is the only TM that accepts L(M) = { } = empty ... of the TM, whose decimal value must be less than 100. Binary Encoding:- 0no of states10no of input symbol10no of tape symbol1... like this other information. Ryt??

1. {<M,w>| M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')}2. {<M>| M is a TM, and M is the only TM that ...

Shubhanshu

960 views

Shubhanshu asked Sep 19, 2017

2 votes

0 answers

283

Practice Question #3
A considered the sets of TMs describing all the Hamiltonian cycle problems, Choose the correct statement, 1) The membership problem of S is decidable. 2) It is decidable if the complement of S is empty. 3) It is decidable if S is empty, finite or infinite. 4) It is decidable if S = ∑*.

A considered the sets of TMs describing all the Hamiltonian cycle problems, Choose the correct statement,1) The membership problem of S is decidable.2) It is decidable if...

AnilGoudar

338 views

AnilGoudar asked Sep 18, 2017

0 votes

1 answer

284

Practice Question #2
A is given a four counter machines M1 accepting a language L1, a pushdown tape machine M2 accepting a language L2 and a TM M3 which cannot have more than 10 states and accepting a language L3. Choose correct statement, 1) The halting problem for M1, M2 and M3 are always decidable. ... decidable if L1 = L2 = L3. 3) It is decidable if L1 = L2 = L3 = ∑* 4) M3 can simulate any TM.

A is given a four counter machines M1 accepting a language L1, a pushdown tape machine M2 accepting a language L2 and a TM M3 which cannot have more than 10 states and ac...

AnilGoudar

263 views

AnilGoudar asked Sep 18, 2017

2 votes

1 answer

285

Decidable or undecidable
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?

If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?

adwaitLP

2.2k views

adwaitLP asked Sep 13, 2017

3 votes

2 answers

286

theory of computation
$L=\{\langle M \rangle\mid M$ is a TM such that if $M$ accepts $w$ then $M$ accepts $ww$ also$\}$ Which of the following is correct? $L$ is decidable $L$ is recognizable but undecidable $L$ is unrecognizable and $\bar L$ is decidable $L$ is unrecognizable and $\bar L$ is undecidable

$L=\{\langle M \rangle\mid M$ is a TM such that if $M$ accepts $w$ then $M$ accepts $ww$ also$\}$ Which of the following is correct? $L$ is decidable$L$ is recognizable ...

The Technical Guy

694 views

The Technical Guy asked Sep 12, 2017

11 votes

2 answers

287

$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$

My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...

sourav.

4.5k views

sourav. asked Sep 9, 2017

0 votes

0 answers

288

Decidable or not?
I think that answer should be decidable.

I think that answer should be decidable.

Xylene

194 views

Xylene asked Sep 9, 2017

8 votes

0 answers

289

Decidable problems concerning Turing machine
Can someone please verify my answers on the following given languages? Please note that RE=Recursive Enumerable, LBA=Linear Bounded Automata, and TM=Turing Machine ... I am more interested to know which problems are Recursive Enumerable and which are Non-Recursive Enumerable.

Can someone please verify my answers on the following given languages?Please note that RE=Recursive Enumerable, LBA=Linear Bounded Automata, and TM=Turing Machine$\text{H...

Manu Thakur

817 views

Manu Thakur asked Sep 9, 2017

1 votes

1 answer

290

decidability

Sunil8860

411 views

Sunil8860 asked Sep 4, 2017

4 votes

1 answer

291

decidability
C = { <G,x> | G is a CFG and x is substring of some y ∈ L(G) } . Then C is - a) undecidable b) Turing unrecognizable c) Recursive enumerable d) decidable

C = { <G,x | G is a CFG and x is substring of some y ∈ L(G) } . Then C is -a) undecidable b) Turing unrecognizable c) Recursive enumerable d) decidable

amrendra pal

378 views

amrendra pal asked Aug 22, 2017

3 votes

2 answers

292

decidability
C = { <G,k> | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be- a) decidable b) Turing unrecognizable c) Recursive enumerable d) undecidable

C = { <G,k | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be-a) decidableb) Turing unrecognizablec) Recursive enumerabled) undecidab...

amrendra pal

1.0k views

amrendra pal asked Aug 22, 2017

3 votes

1 answer

293

decidability
S = { < R > | R is a regular expression describing a language containing at least one string w has 111 as a substring (i.e., w = x111y for some x ans y)}. Then what will be S - a) decidable b) undecidable c) Recursive enumerable d) Turing unrecognizable

S = { < R | R is a regular expression describing a language containing at least one string w has 111 as a substring (i.e., w = x111y for some x ans y)}. Then what will b...

amrendra pal

660 views

amrendra pal asked Aug 20, 2017

7 votes

3 answers

294

decidability
A = { <M> | M is a DFA that accepts some string with more 1s than 0s }. Then A is - a) undecidable b) recursive enumerable c) decidable d) none of the above

A = { <M | M is a DFA that accepts some string with more 1s than 0s }. Then A is - a) undecidable b) recursive enumerablec) decidabled) none of the above

amrendra pal

1.7k views

amrendra pal asked Aug 20, 2017

3 votes

3 answers

295

decidability
A = { <R,S> | R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A - a) Turing recognizable b) decidable c) undecidable d) Turing unrecognizable

A = { <R,S | R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A -a) Turing recognizableb) decidablec) undecidabled) Turing unrecognizable

amrendra pal

2.2k views

amrendra pal asked Aug 20, 2017

3 votes

2 answers

296

decidability
INFINITEDFA= {<A> | A is a DFA and L(A) is an infinite language } . Then - a) INFINITEDFA is decidable. b) INFINITEDFA is undecidable. c) INFINITEDFA is Turing-recognizable. d) INFINITEDFA is Turing-unrecognizable.

INFINITEDFA= {<A | A is a DFA and L(A) is an infinite language } . Then -a) INFINITEDFA is decidable.b) INFINITEDFA is undecidable.c) INFINITEDFA is Turing-recognizable.d...

amrendra pal

728 views

amrendra pal asked Aug 20, 2017

2 votes

1 answer

297

decidability
INFINITEPDA = {<M> | M is a PDA and L(M) is an infinite language } . Then - a) INFINITEPDA is undecidable. b) INFINITEPDA is decidable. c) INFINITEPDA is recursive enumerable. d) INFINITEPDA is Turing co-recognizable.

INFINITEPDA = {<M | M is a PDA and L(M) is an infinite language } . Then -a) INFINITEPDA is undecidable.b) INFINITEPDA is decidable.c) INFINITEPDA is recursive enumerable...

amrendra pal

875 views

amrendra pal asked Aug 20, 2017

5 votes

2 answers

298

decidability
E={<M> | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

E={<M | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

amrendra pal

564 views

amrendra pal asked Aug 20, 2017

1 votes

2 answers

299

Decidability
True/False? The complement of every Turning decidable language is Turning decidable

True/False? The complement of every Turning decidable language is Turning decidable

Sunil8860

751 views

Sunil8860 asked Aug 16, 2017

1 votes

1 answer

300

DECIDABILITY
Is complement of language same type or not decidable by CFL and recursive language or not??? Grammar is ambiguous or not? Grammar in regular/CFL/rel decidable or not?

Is complement of language same type or not decidable by CFL and recursive language or not???Grammar is ambiguous or not?Grammar in regular/CFL/rel decidable or not?

learner_geek

1.4k views

learner_geek asked Aug 15, 2017

Page:

« prev
1
...
5
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: