Theory of ComputationPU Spring 2024
a) State the halting theorem and give the outline of its proof. b) What are P, NP and NP Complete problems? Explain with examples. .
15- a) State the halting theorem and give the outline of its proof.
- b) What are P, NP and NP-Complete problems? Explain with examples. .
A worked answer is on its wayMeanwhile, read the Theory of Computation notes for this topic.
Discussion
Loading…
More Theory of Computation questions
a) Convert the following NFA to its equivalent DFA. 3 TASER RG ta é i EN Se Be aN Nina Des PADRE NS cog SO meclpa tN © wine Hep NE See eal i nab! ae (@) aC ;…PU Spring 202420a) What is CFG? Design CFG for language L=a"b"; m =1, n =1 . Test the grammar for derivation of aaaabbb and also draw equivalent parse tree. b) Convert the…PU Spring 202415a) Define PDA with block diagram. Design a PDA which accepts the language L=a"" : n =1 and test for strings aaaaaaaa and aaaaaa. b) Show that the language L=…PU Spring 20248a) Define Turing machine. Design a Turing machine that accepts the language L= a"b’c" : n =0. b) How does a Turing machine compute a function of natural…PU Spring 202415Write short notes on: (Any two) 2x5 a) Simplification of CFG b) Recursive and Recursively Enumerable Language ¢ c) Decision algorithm for CFLPU Spring 2024a) Define alphabet, string, and language with examples. hs b) Design a DFA for the language L = w € (a, b)" : w ends with bb hs c) Define an ambiguous…PU Spring 20235