TOC-decidability

Aegon asked Sep 23, 2016

457 views

1 votes

If L₁<= L₂

In which of the following cases it is undecidable?

A. L₁ and L₂are DCFL's

B. L₁ and L₂are recursive

C. L₁ and L₂are regular

D. Both A and B

Theory of Computation
decidability

+ –

Aegon asked Sep 23, 2016

Aegon

457 views

See all

1 1 comment

Kapil

commented Sep 23, 2016

What is L₁<= L₂?

Are you saying subset ?

1 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

1 votes

Option D will be right option for it.

Bcz equality(L1==L2) problem in the case of the recursive as well as DCFL always undecidable.In all the cases the regualar languages are decidable.

Paras Nath answered Sep 24, 2016

Paras Nath

See all

1 1 comment

Sushant Gokhale

commented Oct 17, 2016

Its not equality. Its saying L1 is reducible to L2. So option A is correct.

0 votes

Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

0 votes

0 answers

aambazinga asked Sep 8, 2018

433 views

TOC Decidability
How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?

How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?

aambazinga

433 views

aambazinga asked Sep 8, 2018

Theory of Computation
theory-of-computation
decidability
co-turing-recognizable

+ –

1 votes

1 answer

aambazinga asked Sep 8, 2018

390 views

TOC DECIDABILITY
Let E={<M>| M is a DFA that accepts some strings with more 1's than 0's} Show that E is decidable. How can E be decidable. How can a DFA compare between number of 1's and 0's. From the question I know that it's not talking about all, but some. The things is even some should not be decidable. isn't it?

Let E={<M>| M is a DFA that accepts some strings with more 1's than 0's}Show that E is decidable.How can E be decidable. How can a DFA compare between number of 1's and 0...

aambazinga

390 views

aambazinga asked Sep 8, 2018

Theory of Computation
theory-of-computation
decidability
finite-automata

+ –

2 votes

2 answers

manisha11 asked Aug 10, 2018

772 views

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

772 views

manisha11 asked Aug 10, 2018

Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine

+ –

1 votes

1 answer

gauravkc asked Apr 25, 2018

5,999 views

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

Theory of Computation
decidability
theory-of-computation
turing-machine

+ –

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

1 1 comment reply

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

1 1 comment reply

Please log in or register to add a comment.

Related questions

1 1 comment

1 1 comment