Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

P3 is decidable if P3 is reducible to P2's complement

P3 is decidable if P1 is reducible to P3

P3 is undecidable if P3 is reducible to P2

P3 is undecidable if P2 is reducible to P3

Consider three decision problems P1, P2 and P3. It is known that P1 is

1.	Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
A.	P3 is decidable if P1 is reducible to P3
B.	P3 is undecidable if P3 is reducible to P2
C.	P3 is undecidable if P2 is reducible to P3
D.	P3 is decidable if P3 is reducible to P2's complement
Answer» D. P3 is decidable if P3 is reducible to P2's complement

Discussion

No Comment Found

Related MCQs

Consider the translation scheme shown belowS → T RR → + T {print ('+');} R | εT → num {print (num.val);}Here num is a token that represents an integer and num.val represents thecorresponding integer value. For an input string '9 + 5 + 2', this translation scheme willprint
Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
Consider the intermediate code given below:1. i = 12. j = 13. t1 = 5 * i4. t2 = t1 + j5. t3 = 4 * t26. t4 = t37. a[t4] = –18. j = j + 19. if j
Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
The expression (a*b)* c op........ where 'op' is one of '+', '*' and '↑' (exponentiation) can be evaluated on a CPU with a single register without storing the value of (a * b) if
For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
Consider the following statements related to compiler construction : I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata. II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct?
Consider the following two problems on undirected graphs:α: Given G(V,E), does G have an independent set of size |v|—4?β: Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE?
Consider the regular language L =(111+11111)*. The minimum number of states
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

Discussion

No Comment Found

Related MCQs

Reply to Comment