For each of these problems, or languages, give its best known computational clas
ID: 3716253 • Letter: F
Question
For each of these problems, or languages, give its best known computational class. For example, the answer could be P, NP, NP-complete, P-space, recursive, recursively enumerable, to name just a few. For example, if a prblem is known to be in the class NP, but is not known to be in P, and is also not known to be NP-complete, you answer would be “NP.” If there is no class with a standard de?nition which contains the problem, you can say, “Not a member of any class that I can ?nd.” That could be the correct answer!
a)Doea a context-free grammar generate all string? More specifically, given a context- free grammar G where ? is the set of terminals of G, is it true that L(G) = ???
b)Given an n × n checkerboard, for some n, and given a configuration of checkers on that board, can the black player win?
c)Given a Turing machine M and a number t, will M halt within t steps?
Explanation / Answer
a) Decidable : Given a Context-Free grammar G, we can look for useless symbols in grammar. If all the symbols of a production of grammar are useless, surely the language generated by the Context-free Grammar is empty, otherwise not.
“Not a member of any class that I can ?nd.
b) NP-Complete
c) Decidable: M can either accept, go into loop or halt within t steps(which are finite). So within t steps, we are guaranteed to get an answer whether a string will be accepted or not. So this is Decidable and solve in polynomial time. ( P)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.