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

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

1 | M-70777 (S14)-1403

Roll No. Total No. of Pages : 02
Total No. of Questions : 09
MCA (2014 Batch) (Sem.?3)
THEORY OF COMPUTATION
Subject Code : MCA-305B
M.Code : 70777
Time : 3 Hrs. Max. Marks : 100
INSTRUCTIONS TO CANDIDATES :
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. a) Show, by mathematical induction that for all n ? 1.

b) 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 ?-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 ?-
transitions. How will you remove the ?-transitions?
4. What is pumping lemma for regular languages? Use it to prove that the language
L = {0
n
1
n
: n ? 1} is not regular.
SECTION-C
5. Design a Push Down automata for accepting the language L = {0
n
1
n
: n ? 1}.
6. Justify the statement : ?The intersection of two context-free language may not be a
context-free language?.
( 1)
1 2 3 ...
2
n n
n
?
? ? ? ? ?
FirstRanker.com - FirstRanker's Choice
1 | M-70777 (S14)-1403

Roll No. Total No. of Pages : 02
Total No. of Questions : 09
MCA (2014 Batch) (Sem.?3)
THEORY OF COMPUTATION
Subject Code : MCA-305B
M.Code : 70777
Time : 3 Hrs. Max. Marks : 100
INSTRUCTIONS TO CANDIDATES :
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. a) Show, by mathematical induction that for all n ? 1.

b) 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 ?-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 ?-
transitions. How will you remove the ?-transitions?
4. What is pumping lemma for regular languages? Use it to prove that the language
L = {0
n
1
n
: n ? 1} is not regular.
SECTION-C
5. Design a Push Down automata for accepting the language L = {0
n
1
n
: n ? 1}.
6. Justify the statement : ?The intersection of two context-free language may not be a
context-free language?.
( 1)
1 2 3 ...
2
n n
n
?
? ? ? ? ?
2 | M-70777 (S14)-1403

SECTION-D
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 :
a) Is the expression (1* ? ?) regular? Justify your answer.
b) What is structural Induction?
c) State Kleen?s Theorem.
d) Give an example of a regular grammar.
e) What is a derivation tree?
f) What is deterministic push down automata?
g) What is parsing?
h) Give the CFG for the language L = {0
n
1
n
: n ? 0}.
i) What is partial function?
j) 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.
FirstRanker.com - FirstRanker's Choice