Download PTU B.Tech 2021 Jan CSE 7th Sem 71894 Theory Of Computation Question Paper

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

---