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

This post was last modified on 22 March 2020