Download PTU MCA 2020 Dec 3rd Sem 74078 Theory Of Computation Question Paper

Download PTU I. K. Gujral Punjab Technical University (IKGPTU) MCA (Master of Computer Applications) 2020 December 3rd Sem 74078 Theory Of Computation Previous Question Paper

Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
MCA (E-I) (2015 to 2018) (Sem.?3)
THEORY OF COMPUTATION
Subject Code : MCA-305B
M.Code : 74078
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O CANDIDAT ES :
1 .
SECT IONS-A, B, C & D c ontains TWO questions eac h carrying TEN marks each
and students have to attempt any ONE question fro m ea ch SECT ION.
2 .
SECT ION-E is C OMPULSORY consisting of T EN ques tions ca rryin g TWENTY
marks in all.
SECTION-A
Q1 a) Discuss one-one onto function by taking suitable example.
n(n 1)
b) Prove that
(n 1
)
using mathematical induction.
2
Q2 Design an automaton accepting all the strings ending with bb. Where { ,
a }
b .
SECTION-B
Q3 a) Construct a DFA for the regular expression (0+10)* 101(0+10)*.
b) Design a DFA accepting language
{ n
L
a bb | n 1&{a, }
b }
Q4 Construct a CFG for
{ n m p
L
a b c | n m p, p 1&{a, ,
b }
c }
SECTION-C
Q5 Explain the following :
a) Ambiguity in CFG
b) DPDA
Q6 Show that language L = [anbncn | n 0 &{a,b,c} } is not context free
1 | M-74078
(S6)-730

---

SECTION-D
Q7 Design a Turing Machine which recognizes palindromes over {0,1}.
Q8 Explain the following :
a) Multitape Turing Machine
b) Chomsky Hierarchy
SECTION-E
Write briefly :
Q9 State pumping lemma for regular languages.
Q10 Discuss the concept given by Arden's theorem.
Q11 What is meant by regular expression?
Q12 Define a Derivation Tree for a CFG.
Q13 What are two normal forms for a CFG?
Q14 Define Acceptance of PDA by Empty Stack.
Q15 What is halting problem of Turing Machine?
Q16 Compare PDA and TM.
Q17 Write two properties of recursively enumerable languages.
Q18 Define NP complete problem.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
2 | M-74078
(S6)-730

---