We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution 
+ Link For Past Papers, Solved MCQs, Short Notes & More 
Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
CS701 Theory of Computation Short Question & Answers
Tags:
+ How to Follow the New Added Discussions at Your Mail Address?
+ How to Join Subject Study Groups & Get Helping Material? + How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators? + VU Students Reserves The Right to Delete Your Profile, If?.
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)Q1: Show that A_{TM} is not mapping reducible to E_{TM}. 10 marks Spring 2016 – Mid


Q2: Let L_{ALL} = {M is a TM with input alphabet ∑ and L(M)∑*}, prove that L_{ALL}is not Turing recognizable. 10 marks Spring 2016 – Mid


Q3: In the Silly Post Correspondence Problem (SPCP), in each pair the top string has the same length as the bottom string. Show that the SPCP is decidable, 10 marks Spring 2016 – Mid


Q4: Lets recall that a language A is Truing recognizable if there is a TM M such that L(M)=A. 5 marks Spring 2016 – Mid


Q5: Let X be the set{1,2,3,4,5} and Y be the set (6,7,8,9,10}. We describe the functions f:(X>Y) and g:(X>Y) in the following table.
(d). Is g onetoone? (e). Is g onto? (f) Is g a correspondence? Spring 2016 – Mid


Q6: Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable, using a proof by diagonalization. 10 marks Spring 2016 – Mid


Q7: Show that the set of possible statements in TH(N,+,X) is turing recognizable. 10 marks Spring 2016 – Mid


Q8: if ∀Y∃X[R_{1}(x,x,y)], if we assign plus to (a,c,c) whenever a+b=c. if R is (universe) real number then whether the sentence is TRUE, justify you answer. 10 marks Spring 2016 – Mid


Q9: Show that the set of all off all odd integers has onetoone correspondence with the set of all even integers. 5 marks Spring 2016 – Mid


Q10: Show that all positive numbers has onetoone correspondence to real number. 5 marks Spring 2016 – Mid


Q11: if A belong to a language that contains infinity pairs, prove that its uncountable. 5 marks Spring 2016 – Mid


Q12: Consider following instance of PCP. Is it possible to find a match? If YES then give the dominos arrangements, If NO then prove. 5 marks 1/0, 101/1, 1/001 Spring 2016 – Mid


Q13: Show that 234 and 399 are relatively prime or not. 5 marks Spring 2016 – Mid


Q14: Show that some TRUE statements in TH(N,+,X) are not proveable. 10 marks Spring 2016 – Mid


Q15: Is PCP decidable over unary alphabet? 5 marks Spring 2016 – Mid


Q16: Show that A≤_{T}B and B≤_{T}C then A≤_{T}C. 10 marks Spring 2016 – Mid


Q17: Prove that Turing recogniable languages are closed under concatenation. 10 marks Fall 2015 – Mid

Q18: Show that directed Hamiltonian cycle is NPComplete. 10 marks Spring 2016 – Final

Q19: Prove cycle length problem is NLComplete. 10 marks Spring 2016 – Final

Q20: Let CNF_{K} = {<?>  ? is a satisfiable CNFFormula where each variable appears in at most k places}. 15 marks 1. Show that CNF2 ∈ P. 2. Show that CNF3 ∈ NPcomplete. Spring 2016 – Final

Q21: A directed graph is strongly connected if every two nodes are connected by a directed path in each direction. Let STRONGLYCONNECTED = { G is a strongly connected graph}. Show that STRONGLYCONNECTED is NLcomplete. 10 marks Spring 2016 – Final

Q22: Show that A_{LBA} is PSpace Complete. 10 marks Spring 2016 – Final

Q23: Let ADD={(x,y,z)  x,y,z > 0 are binary integers and x+y=z}. Show that ADD ∈ LSPACE. 10 marks Spring 2016 – Final

Q24: Let t(n) be a function where t(n) ≥ n , Show that t(n) time k tape TM has an equivalent O(t^{2}(n)) time single tape TM. 10 marks Spring 2016 – Final

Q25: Show that 3Color problem is in NP Complete. 10 marks Spring 2016 – Final

Q26: Show that E_{DFA} is in NLComplete. 10 marks Spring 2016 – Final

Q27: Graphs G and H are called isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {<g, h=""> G and H are isomorphic graphs}. Show that ISO is in NP. 10 marks Spring 2016 – Final

Q28: Let SETSPLITTING = {<s,c> S is a finite set and C = {C_{1}, ... ,C_{k}} is a collection of subsets of S, for some k > 0, such that elements of S can be colored red or blue so that no C_{i} has all its elements colored with the same. Show that SETSPLITTING is in NP. 10 marks Spring 2016 – Final

Q29: Find Maxclique in DP. 10 marks Spring 2016 – Final

Q30: Let CONNECTED={G is connected undirected graph}. Show that it is in P. 10 marks Spring 2016 – Final

Q31: Let HALFCLIQUE = { G is an undirected graph having a complete subgraph with at least m/2 nodes, where m is the number of nodes in G}. Show that Half Clique is in NPcomplete. 10 marks Spring 2016 – Final

Q32: Show that, if P = NP, then every language A is in P, except A = ∅ and A = ∑*, is in NPcomplete. 10 marks Spring 2016 – Final

Q33: Let PALADD = {<x, y=""><x, y>  x, y > 0 are binary integers, where x + y is an integer whose binary representation is palindrome}. Show that PALADD ϵ LSPACE. 10 marks Spring 2016 – Final

© 2019 Created by + M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
VU Students reserves the right to delete any profile, which does not show any Activity at site nor has not any activity more than 01 month.
We are usergenerated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List  Moderators Group
All Members  Featured Members  Top Reputation Members  Angels Members  Intellectual Members  Criteria for Selection
Become a Team Member  Safety Guidelines for New  Site FAQ & Rules  Safety Matters  Online Safety  Rules For Blog Post