Register

Complement of a language which is recursively enumerable but not recursive

2,563 views
2 2 votes
What is the complement of a language which is recursively enumerable but not recursive? Is it only non rel or can be both both non rel and recursive?

1 Answer

4 4 votes
Complement of RE but not REC is  Non-RE.

Complement of Non-RE may or may not be RE (but never REC).

If (L is RE and L' is complement of RE and both L and L' are RE) then both L and L' are REC.
Voting & Accepting an answer helps improve the community
← Previous · ME test SeriesNext → · ME TEST
← Previous in category · Self DoubtNext in category → · ME test Series
Position:
Show:

Related questions

2 2 votes
0 0 answers
785
785 views
Meenakshi Sharma asked Oct 10, 2018
785 views
example of language which is recursive but not context sensitive
can someone explain diff between REC , Rec enumerable and context sensitive language with clear examplelike language is RE but not not REC and REC but not CSL
25 25 votes
1 answers 1 answer
8.9k
8.9k views
Vikrant Singh asked Jan 27, 2015
8,860 views
Which of the following languages are Recursively Enumerable language?
Which of the following languages are Recursively Enumerable language?$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which...
0 0 votes
2 2 answers
1.6k
1.6k views
radha gogia asked Nov 20, 2015
1,608 views
Which of the following properties of a Recursively enumerable set L is/are recursively enumerable?
A) L is regularB) L is finiteC) L is set of palindromes
0 0 votes
0 0 answers
601
601 views
Sanjay Sharma asked Apr 15, 2017
601 views
which of the following is not primitive recursive but computable