Non Monotonicity : Undecidability, Non RE

CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty}Which of the following is true?a- Decidable RECB- Undecidable and REc-Undecidable and non REd- Decidable ...

bts1jimin

623 views

bts1jimin asked Jan 8, 2019

Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages

+ –

0 votes

0 answers

Rajesh R asked Dec 8, 2017

611 views

Difference between Co-RE and Non RE language.
Can someone please tell me the difference between Non R.E and CoRE language ?

Can someone please tell me the difference between Non R.E and CoRE language ?

Rajesh R

611 views

Rajesh R asked Dec 8, 2017

Theory of Computation
theory-of-computation

+ –

2 votes

1 answer

srestha asked Jan 29, 2017

1,728 views

RE or Non RE
1) Language describing the ambiguity of CFG is RE or Non RE? 2) Language describing the non-ambiguity of a CFG (whether a given CFG is non-ambiguous) and complement of the language of ambiguity of CFG are RE or Non RE? 3) Inherent Ambiguity of CFL is RE or Non RE? 4) Is language of the complement of Ambiguity and the language of non-ambiguity of CFG same?

1) Language describing the ambiguity of CFG is RE or Non RE?2) Language describing the non-ambiguity of a CFG (whether a given CFG is non-ambiguous) and complement of the...

srestha

1.7k views

srestha asked Jan 29, 2017

Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages

+ –

7 votes

2 answers

Manu Thakur asked Nov 15, 2014

3,114 views

Given Language is REC or Non RE
Which of the following is true for the given language? $L=$ {<TM> | TM halts on every input} <TM> is encoding of the Turing machine (A) $L$ is Recursive and $\overline{L}$ is also Recursive (B) $L$ is Recursive ... Enumerable and $\overline{L}$ is Recursive Enumerable (D) $L$ is Non Recursive Enumerable and $\overline{L}$ is Non Recursive Enumerable

Which of the following is true for the given language?$L=$ {<TM | TM halts on every input}<TM is encoding of the Turing machine(A) $L$ is Recursive and $\overline{L}$ is ...

Manu Thakur

3.1k views

Manu Thakur asked Nov 15, 2014

Theory of Computation
theory-of-computation
difficult
recursive-and-recursively-enumerable-languages
decidability

+ –

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

2 2 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

2 2 Comments