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. (x)Every context-free language is in P (xi)Every context-sensitive language is in P. (xii) Every language generated by a general grannnar is recursive. (xii)Every language accepted by a non-deterministic machine is accepted by some deterministic machine. xiv) The problem of whether two given context-free grammars generate the same language is decidable. (xv) (xv) The problem of whether a given string is generated by a given context-free grammar is decidable (xvi) If G is a context-free grainmar, the question of whether L(G) = 0 is decidable.

Explanation / Answer

x: True because context free language is decidable
xi: True because context sensitive language is decidable.
This is because we can simulate them on their respective machine and check whether or not the language is solvable.
xii: False. It might also be recursively enumerable but not recursive.
xiii: False. NPDA can accept some context free languages that are not accepted by its deterministic version, DPDA.
xiv: False. The equivalence problem for various families of languages is of great interest in the theory of formal languages. This problem is decidable for regular languages (Rabin and Scott, 1959) and undecidable for context-free languages (Bar-Hillel et al., 1961).
xv: True. Membership problem is decidable for context free languages.
xvi: True. Emptiness problem is decidable for context free languages.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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