Theory of ComputationPU Spring 2023
Write short notes on: (Any two) 2x5 a) Pumping lemma for CFL b) Universal Turing Machine c) The Halting problem 2
Write short notes on: (Any two) 2x5
- a) Pumping lemma for CFL
- b) Universal Turing Machine
- c) The Halting problem 2
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 202415a) State the halting theorem and give the outline of its proof. b) What are P, NP and NP Complete problems? Explain with examples. .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 2024