We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ 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.

CS-701 Theory of Computation Short Question & Answers

+ 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?


See Your Saved Posts Timeline

Views: 810

.

+ 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)

Replies to This Discussion

Q1: Show that ATM is not mapping reducible to ETM. 10 marks
Spring 2016 – Mid
 
Q2: Let LALL = {M is a TM with input alphabet ∑ and L(M)∑*}, prove that LALLis 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.
N 1 2 3 4 5
F(n) 6 7 6 7 6
N 1 2 3 4 5
G(n) 10 9 8 7 6
(a) Is f one-to-one?          (b) Is f onto?       (c) Is f a correspondence?
(d). Is g one-to-one?        (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[R1(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 one-to-one correspondence with the set of all even integers. 5 marks
Spring 2016 – Mid
Q10: Show that all positive numbers has one-to-one 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≤TB and B≤TC then A≤TC. 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 NP-Complete. 10 marks
Spring 2016 – Final
 
Q19: Prove cycle- length problem is NL-Complete. 10 marks
Spring 2016 – Final
 
Q20: Let CNFK = {<?> | ? is a satisfiable CNF-Formula where each variable appears in at most k places}. 15 marks
1. Show that CNF2 ∈ P.
2. Show that CNF3 ∈ NP-complete.
Spring 2016 – Final
 
Q21: A directed graph is strongly connected if every two nodes are connected by a directed path in each direction. 
Let STRONGLY-CONNECTED = { |G| is a strongly connected graph}. 
Show that STRONGLY-CONNECTED is NL-complete. 10 marks
Spring 2016 – Final
 
Q22: Show that ALBA is P-Space 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(t2(n)) time single tape TM. 10 marks
Spring 2016 – Final
Q25: Show that 3-Color problem is in NP Complete. 10 marks
Spring 2016 – Final
Q26: Show that EDFA is in NL-Complete. 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 SET-SPLITTING = {<s,c> |S| is a finite set and C = {C1, ... ,Ck} 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 Ci has all its elements colored with the same. Show that SET-SPLITTING is in NP. 10 marks
Spring 2016 – Final
 
Q29: Find Max-clique 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 HALF-CLIQUE = { |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 NP-complete. 10 marks
Spring 2016 – Final
Q32: Show that, if P = NP, then every language A is in P, except A = ∅ and A = ∑*, is in NP-complete. 10 marks
Spring 2016 – Final
Q33: Let PAL-ADD = {<x, y=""><x, y> | x, y > 0 are binary integers, where x + y is an integer whose binary representation is palindrome}. 
Show that PAL-ADD ϵ LSPACE. 10 marks
Spring 2016 – Final

answers?

RSS

Latest Activity

+ ՏhehαrZααD + liked + !! "AS" !!'s discussion Jis Tarah ..
1 hour ago
Pronoun liked zobialatif's discussion hazrat ali says
1 hour ago
٥ دن updated their profile
2 hours ago
+ !! "AS" !! replied to + !! "AS" !!'s discussion Jis Tarah ..
2 hours ago
Siddiq khan kakar liked + M.Tariq Malik's discussion PAK301 Pakistan Studies Short Notes, PAK301 Solved Subjective Questions, PAK301 Solved MCQs
2 hours ago
Siddiq khan kakar liked + M.Tariq Malik's group PAK301 Pakistan Studies
2 hours ago
+ ! ! JS ! ! + posted a discussion
2 hours ago
Siddiq khan kakar liked Siddiq khan kakar's discussion RIP
2 hours ago
Kashif Iqbal added 2 discussions to the group FIN624 Islamic Mode of Financing
2 hours ago
+ ! ! JS ! ! + liked + Iuuoɔǝut +'s discussion جلوۂ عشق حقیقت تھی حسن مجاز بہانہ تھا
2 hours ago
+ ! ! JS ! ! + liked + !! "AS" !!'s discussion Baat Karna ...
2 hours ago
+ ! ! JS ! ! + liked + !! "AS" !!'s discussion Ghalti...
2 hours ago
+ ! ! JS ! ! + liked + !! "AS" !!'s discussion Yaha Har Cheez ..
2 hours ago
+ ! ! JS ! ! + liked +!!!StRaNGeR!!! +'s discussion ﺁﭖ ﺩﻝ ﺟﻮﺋﯽ ﮐﯽ ﺯﺣﻤﺖ ﻧﮧ ﺍﭨﮭﺎﺋﯿﮟ ، ﺟﺎﺋﯿﮟ
2 hours ago
+ ! ! JS ! ! + liked + !! "AS" !!'s discussion Alfaaz Ki Nisbat..
2 hours ago
+ ! ! JS ! ! + liked + !! "AS" !!'s discussion Jis Tarah ..
2 hours ago
Siddiq khan kakar posted discussions
2 hours ago
+ ! ! JS ! ! + replied to + !! "AS" !!'s discussion Jis Tarah ..
3 hours ago
Zain Arshad replied to + M.Tariq Malik's discussion ENG201 Business and Technical English Writing Assignment No 01 Fall 2019 Solution & Discussion in the group ENG201 Business and Technical English Writing
3 hours ago
Nayyab Anwar updated their profile
3 hours ago

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service