True or False. T = true, F = false, and O = open, meaning that the answer is not

Question

True or False. T = true, F = false, and O = open, meaning that the answer is not known science at this time. In the questions below, P and NP denote P-time and NP-time, respectively. (xvii) If G is a context-free grammar, the question of whether L(G) = . is decidable, where is the terminal alphabet of G. (xviii) The set of all fractions whose values are less than is decidable. (A ruction is a string, defined to be a non-empty string of decimal digits followed by a slash followed by a non-empty string of decimal digits, such as "3/42") xix) There exists a polynomial time algorithm which finds the factors of any positive integer, where the input is given as a unary ("caveman") numeral. (xx) For any two languages L1 and L2, if L1 is undecidable and there is a recursive reduction of L1 to L2, then L2 must be undecidable. (xxi) For any two languages Ly and L, if L2 is undecidable and there is a recursive reduction of to L2, then L must be undecidable. (xxii) As you may have learned, there is a formal language which can be used to write any mathematical proposition as well as any proof of any mathematical proposition. In 1978, Jack Milnor told me that in the future no proof will be accepted unless it can be verified by a computer If P is a mathematical proposition that can be written using string of length n, and P has a proof, then P must have a proof whose length is 0(22 (xxii) There is a P-TIME reduction of the context-free grammar membership problem to the halting problem

Explanation / Answer

[1] TRUE [Theorm 4.9 Every context-free language is decidable]
[2] FALSE
[3] TRUE
[4] TRUE
[5] TRUE
[6] OPEN
[7] TRUE

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.