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

Roll No.

Total No. of Questions: 18

Total No. of Pages : 02

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

MCA (E-I) (2015 to 2018) (Sem.-3)

THEORY OF COMPUTATION

Subject Code : MCA-305B

M.Code: 74078

Time: 3 Hrs.

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

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

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

Q1 a) Discuss one-one onto function by taking suitable example.

b) Prove that ?(x-1 = n(n-1)) using mathematical induction.

2

Q2 Design an automaton accepting all the strings ending with bb. Where {a,b} ?S.

SECTION-B

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

Q3 a) Construct a DFA for the regular expression (0+10)* 101(0+10)*.

b) Design a DFA accepting language L = {a"bb|n=1& {a,b} ? S}

Q4 Construct a CFG for L = {aⁿb^mc^p \n + m = p, p > 1& {a,b,c} ? S}

SECTION-C

Q5 Explain the following :

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

a) Ambiguity in CFG

b) DPDA

Q6 Show that language L = [a"b"c" | n = 0 &{a,b,c} ? S } is not context free

SECTION-D

Q7 Design a Turing Machine which recognizes palindromes over {0,1}.

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

Q8 Explain the following :

a) Multitape Turing Machine

b) Chomsky Hierarchy

SECTION-E

Write briefly :

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

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?

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

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.

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

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.

Get previous year question papers at FirstRanker.com