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

Roll No. _________________________ Total No. of Pages : 02

Total No. of Questions : 09

MCA (2014 Batch) (Sem.-3)

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

THEORY OF COMPUTATION

Subject Code : MCA-305B

M.Code: 70777

Time: 3 Hrs. Max. Marks : 100

INSTRUCTIONS TO CANDIDATES :

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

1. SECTIONS-A, B, C & D contains TWO questions each carrying TWENTY marks each and students has 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. 1. Show, by mathematical induction that for all n = 1.

      1+2+3+...+n = n(n+1)/2

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

   2. What is an equivalence relation? Explain with an example.
2. Design a finite automata for accepting the strings generated over ? = {0, 1} having even number of 0s and 1s.

SECTION-B

3. What is e-transition? Give an example of an automata having two different final states (other states may be taken as per your choice) and both of them have incoming e-transitions. How will you remove the ?-transitions?

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

4. What is pumping lemma for regular languages? Use it to prove that the language L = {0ⁿ1ⁿ : n = 1} is not regular.

SECTION-C

5. Design a Push Down automata for accepting the language L = {0ⁿ1ⁿ : n = 1}.
6. Justify the statement: "The intersection of two context-free language may not be a context-free language".

SECTION-D

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

7. Design a Turing Machine for the addition of two numbers.
8. What is a recursive language? Give argument(s) in support of the statement : "Recursive languages are closed under complementation".

SECTION-E

9. Answer briefly :
   1. Is the expression (1* - ?) regular? Justify your answer.
   2. What is structural Induction?

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

   3. State Kleen's Theorem.
   4. Give an example of a regular grammar.
   5. What is a derivation tree?
   6. What is deterministic push down automata?
   7. What is parsing?

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

   8. Give the CFG for the language L = {0ⁿ1ⁿ : n = 0}.
   9. What is partial function?
   10. Give an example of CSG.

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.

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

FirstRanker.com