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

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

1 | M-74078 (S6)-1417
Roll No. Total No. of Pages : 02
Total No. of Questions : 09
MCA (E-I) (2015 & Onwards) (Sem.?3)
THEORY OF COMPUTATION
Subject Code : MCA-305B
M.Code : 74078
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS TO CANDIDATES :
1. SECTIONS-A, B, C & D contains TWO questions each carrying TEN marks each
and students have to attempt any ONE question from each SECTION.
2. SECTION-E is COMPULSORY consisting of TEN questions carrying TWENTY
marks in all.

SECTION-A
1. Describe various applications of Finite Automata.
2. Explain the principle of Mathematical and Structural Induction along with the examples.
SECTION-B
3. Draw a FA with epsilon moves that accepts strings over ? ?= { a, b, c} having any number
of a?s followed by any number of b?s followed by any number of c?s.
4. a) Briefly explain Arden's method for the conversion of NFA into DFA with example.
b) Discuss MyHill-Nerode Theorem.
SECTION-C
5. Convert the grammar S ? ABb |a, A? aaA|B, B ? bAb into Greibach Normal Form.
6. Explain the process of Push Down Automata. With the help of example differentiate
between Deterministic vs. Non Deterministic PDA.
SECTION-D
7. Construct a Turing Machine to perform Multiplication.
8. Describe Chomsky Hierarchy of Grammar and indicate their recognizers.
FirstRanker.com - FirstRanker's Choice

1 | M-74078 (S6)-1417
Roll No. Total No. of Pages : 02
Total No. of Questions : 09
MCA (E-I) (2015 & Onwards) (Sem.?3)
THEORY OF COMPUTATION
Subject Code : MCA-305B
M.Code : 74078
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS TO CANDIDATES :
1. SECTIONS-A, B, C & D contains TWO questions each carrying TEN marks each
and students have to attempt any ONE question from each SECTION.
2. SECTION-E is COMPULSORY consisting of TEN questions carrying TWENTY
marks in all.

SECTION-A
1. Describe various applications of Finite Automata.
2. Explain the principle of Mathematical and Structural Induction along with the examples.
SECTION-B
3. Draw a FA with epsilon moves that accepts strings over ? ?= { a, b, c} having any number
of a?s followed by any number of b?s followed by any number of c?s.
4. a) Briefly explain Arden's method for the conversion of NFA into DFA with example.
b) Discuss MyHill-Nerode Theorem.
SECTION-C
5. Convert the grammar S ? ABb |a, A? aaA|B, B ? bAb into Greibach Normal Form.
6. Explain the process of Push Down Automata. With the help of example differentiate
between Deterministic vs. Non Deterministic PDA.
SECTION-D
7. Construct a Turing Machine to perform Multiplication.
8. Describe Chomsky Hierarchy of Grammar and indicate their recognizers.

2 | M-74078 (S6)-1417
SECTION-E
9. Write briefly :
a) Define Recursive Set.
b) Write short note on Turing computable.
c) Define Unambiguous Grammar.
d) What is Primitive Recursive?
e) Explain Automaton.
f) Construct a DFA over ? = (a,b) which produces not more than 3 a s.
g) State the difference between NFA and DFA.
h) Define Strong Induction Principle.
i) Define Pumping Lemma for CFG?.
j) Explain Parse Trees.








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.
FirstRanker.com - FirstRanker's Choice