Download PTU (Punjab Technical University) B.Tech (Bachelor of Technology) / BE (Bachelor of Engineering) 2021 January CSE 7th Sem 71894 Theory Of Computation Previous Question Paper

Roll No.

Total No. of Pages : 02

Total No. of Questions : 18

B.Tech.(CSE) (2012 to 2017) (Sem.?7)

THEORY OF COMPUTATION

Subject Code : BTCS-702

M.Code : 71894

Time : 3 Hrs. Max. Marks : 60

INST RUCT ION TO CANDIDAT ES :

1 .

SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks

each.

2 .

SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents

have to atte mpt ANY FOUR questio ns.

3 .

SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents

have to atte mpt ANY TWO questions .

SECTION-A

Answer Briefly:

1.

Define alphabets in Theory of Computation.

2.

Define Non Deterministic Finite Automata.

3.

What is a transition table?

4.

Discuss Regular Expression.

5.

State pumping lemma for regular languages.

6.

Write short note on decidability.

7.

What is left most derivation?

8.

Write properties of LR(k) grammars.

9.

Compare deterministic and non deterministic versions.

10. Define the language of Turing machine.

1 | M-71894

(S2)- 490

SECTION-B

11. Define the rule for construction of CFG from given PDA.

12. What are the additional features of PDA compared with NFA?

13. Verify whether that the following context free grammar is ambiguous or not :

S 1A0S

S 1A0S1S

A 1

S 0

14. Give pushdown automata that recognize the following languages :

B = {w {0, 1}* | w = wR and the length of w is odd}

15. Describe the recursively Enumerable Language with example?

SECTION-C

16. Write the steps to convert context free grammar into regular expression by taking suitable

example?

17. Explain the extended transition function for NFA, DFA and -NFA. Give the regular

expressions for set of all strings that begin with 110?.

18. Write short note on following :

a) Rules for the conversion of Grammars to PDA

b) Parsing techniques

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.

2 | M-71894

(S2)- 490

This post was last modified on 26 June 2021