MyQuestionIcon

1

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

Equivalence Relation

Consider the ...

Question

Consider the following statements:
1. The complement of every Turning decidable language is Turning decidable.
2. There exists some language which is in NP but is not Turing decidable.
3. If L is a language in NP, L is turing decidable.
Which of the above statements is/are True?

Open in App

Solution

Statement 1: True, because decidable languages (REC) are closed under complement operation.
Statement 2: False, because $P ⫅ N P \subseteq R E C$ .
So every P and every NP language is decidable (REC).
Statement 3: True, every language in NP is decidable.

Suggest Corrections

thumbs-up

0

Similar questions

Q. Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine,there exists an equivalent deterministic Turing machine
2. Turing recognizable languages are closed under union and complemenetation
3. Turing decidable languages are closed under intersection and complemenetation
4. Turing recognizable languages are closed under union and intersection

Q. Consider the following problems regarding decidability.
I. Given a Turing Machine M, whether L(M) is context free.
II. Given a Non-deterministic PDA P, whether there exists a Deterministic Turing Machine M Such that both P and M accept the same languge.
III. Given a deterministic Turing Machine M, wheather there exists a Non Deterministic PDA P such that both P and M accept the same languge.
IV. Given a regular languge L, whether the complement of L is a DCFL
Which of the above problems are decidable ?

Q. Consider the following Turing Machine M over the alphabet {a, b} and tape alphabet

{a, b, □}

The language accepted by the above M is

Q. Nobody knows yet if P = NP. Consider the language L defined as follows
L=

{\begin{matrix} (0 + 1)^{*} i f P = N P ϕ o t h e r w i s e \end{matrix}

Which of the following statements is true?

Q. Consider the following statements:
I. There exists a non deterministic context free language whose reversal is DCFL.
II. There exists a non regular CSL whose Kleene closure is regular.
Which of the above statements are true ?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Types of Relations

MATHEMATICS

Watch in App

explore_more_icon

Explore more

Equivalence Relation

Standard XIII Mathematics

Join BYJU'S Learning Program

CrossIcon