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

Roll No. _________________________ Total No. of Pages : 02

Total No. of Questions : 09

MCA (E-I) (2015 & Onwards) (Sem.-3)

--- Content provided by‌ FirstRanker.com ---

THEORY OF COMPUTATION

Subject Code : MCA-305B

M.Code: 74078

Time: 3 Hrs. Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :

--- Content provided by‌ FirstRanker.com ---

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.

--- Content provided by‍ FirstRanker.com ---

SECTION-B

1. Draw a FA with epsilon moves that accepts strings over S = {a, b, c} having any number of a's followed by any number of b's followed by any number of c's.
2. a) Briefly explain Arden's method for the conversion of NFA into DFA with example.
   b) Discuss MyHill-Nerode Theorem.

SECTION-C

--- Content provided by‌ FirstRanker.com ---

1. Convert the grammar S ? ABb |a, A? aaA|B, B ? bAb into Greibach Normal Form.
2. Explain the process of Push Down Automata. With the help of example differentiate between Deterministic vs. Non Deterministic PDA.

SECTION-D

1. Construct a Turing Machine to perform Multiplication.
2. Describe Chomsky Hierarchy of Grammar and indicate their recognizers.

--- Content provided by⁠ FirstRanker.com ---

SECTION-E

9. Write briefly :
   1. Define Recursive Set.
   2. Write short note on Turing computable.
   3. Define Unambiguous Grammar.
   4. What is Primitive Recursive?

   --- Content provided by⁠ FirstRanker.com ---

   5. Explain Automaton.
   6. Construct a DFA over S = (a,b) which produces not more than 3 a's.
   7. State the difference between NFA and DFA.
   8. Define Strong Induction Principle.
   9. Define Pumping Lemma for CFG?

   --- Content provided by⁠ FirstRanker.com ---

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

--- Content provided by​ FirstRanker.com ---