Download PTU B.Tech 2021 Jan IT 7th Sem 71983 Theory Of Computation Question Paper

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

Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.Tech (Information Technology) (Sem.?7)
THEORY OF COMPUTATION
Subject Code : BTIT-904
M.Code : 71983
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O 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 q ues tions.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
have to atte mpt any T WO questio ns.
SECTION-A
Write briefly :
1.
L * , Justify this formal language expression.
2.
Define the term `Automation'.
3.
What is acceptability of a string by Finite Automation?
4.
What is left recursion?
5.
What is decidability?
6.
State Arden's theorem.
7.
Write rules for writing CNF grammar.
8.
State pumping lemma for CFG.
9.
What are recursively enumerable languages?
10. What is meant by halting problem in TM?
1 | M-71983
(S2)-601

---

SECTION-B
11. Explain Chomsky classification of Grammars with help of examples of each.
12. What do you mean by parsing? How left most and right most derivation helps to find out
the ambiguity in a grammar?
13. Explain Chomsky normal form of CFG with the help of example.
14. Convert the following NDFA to DFA :
a,b
b
b
q0
q1
q2
15. Find out whether the language
n n n
L = x y z | n
1 is context free or not.
SECTION-C
16. What is a context free grammar? Explain closure properties of Context free grammar.
17. What are Turing machines? Explain different ways by which we can represent the Turing
machines.
18. Write a short note on :
a. Recursively Enumerable Languages.
b. LR(K) Grammars
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-71983
(S2)-601

---