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

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

This post was last modified on 22 March 2020