Nobody knows yet if P - NP- Consider the language L defined as followsL-0-1- if P-NP- otherwise -Which of the following statements is true-

If P = NP then L = (0+1)* which is regular. If P ≠ NP then L = ϕ which is a also regular. Either way L is regular and hence recursive. ...

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

Nobody knows ...

Question

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?

Open in App

Solution

Suggest Corrections

Similar questions

L^{i}

L^{0} = {ϵ}

L^{i} = L^{i - 1} \cdot L f o r a l l i > 0

L^{k} = L^{k + 1}

L_{1}

L_{1}

L a n g u a g e L_{1} i s d e f i n e d b y t h e g r a m m a r :

S_{1} \to a S_{1} b | ε

L a n g u a g e L_{2} i s d e f i n e d b y t h e g r a m m a r :

S_{2} \to a b S_{2} | ε

C o n s i d e r t h e f o l l o w i n g i s T R U E ?

P : L_{1} i s r e g u l a r

Q : L_{2} i s r e g u l a r

Which one of the following is TRUE?

S_{1} : \sum^{*} - {ϵ} = \sum^{+}

S_{2} : L^{*} - {ϵ} = L^{*}

L_{1}, L_{2}, L_{3}

L_{1} = {0^{p} 1^{q} | p, q \geq 0}

L_{2} = {0^{p} 1^{q} | p, q \geq 0 and p = q}

L_{3} = {0^{p} 1^{q} 0^{r} | p, q, r \geq 0 and p = q = r}

Join BYJU'S Learning Program