MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

If L and L̅ a...

Question

If L and $¯ L$ are recursively enumerable then L is

Open in App

Solution

There is a theorem which states that whenever L and $¯ L$ are both RE, then both will be REC.

Suggest Corrections

thumbs-up

0

Similar questions

Q. Which of the following problems are decidable?
1. Does a given program ever produce an output?
2. If L is a context-free language,then, is

¯ L

also context-free?
3. If L is a regular language,then,is

¯ L

also regular
4. If L is a recursive language,then,is

¯ L

Q. If A is reducible to B and A is not Recursively Enumerable then B is ______.

Q. For any two language

L_{1} a n d L_{2}

L_{1}

is context free and

L_{2}

is recursively enumerable but not recursive, which of the following is/are necessarily true?
1.

_{1}

L_{1}

) is recursive
2.

_{2}

L_{2}

) is recursive
3.

_{1}

is context-free
4.

_{1} \cup L_{2}

is recursively enumerable

Q. Let L₁be a recursive language. Let L₂ and L₃ be language that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Q. The set of all recursively enumerable language is

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Double circulation / Pulmonary circulation / Oxygenation of Blood

Watch in App

Join BYJU'S Learning Program

CrossIcon