Download PTU B-Tech CSE-IT 2020 Dec 7th Sem 71894 Theory Of Computation Question Paper

Download PTU (I.K.Gujral Punjab Technical University (IKGPTU)) B-Tech (Bachelor of Technology) (CSE-IT)- Computer Science Engineering -Information Technology 2020 December 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 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 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.
Differentiate between NFA and DFA.
2.
What is a transition graph?
3.
What is Chomsky Classification of formal languages?
4.
What is a derivation tree?
5.
What are the basic operations for strings?
6.
Define Union of Two Languages.
7.
What is ambiguity?
8.
Define Mathematical Induction.
9.
Define Terminal and Non-Terminal Symbol.
10. Define Leftmost and Rightmost Derivation.
1 | M-71894
(S2)-1162

---

SECTION-B
11. Give regular expression to each of the subsets of {a,b} :
a) Set of all strings containing exactly 2a's
b) Set of all strings containing substring aa.
12. What is NFA? Show with the help of graph.
13. State pumping lemma for regular sets.
14. What are the steps needed to reduce a context free grammar to an equivalent grammar in
Chomsky Normal Form?
15. Discuss the relation between languages and types of automata with help of diagram.
SECTION-C
16. Give proof for the statement: If L is a context free language, then we can construct a PDA
A accepting L by empty store, i.e. L= N(A).
17. Explain the following :
a) What are properties of regular languages?
b) What is Turing machine and its halting problem?
18. Differentiate with example :
a) Mealy and Moore Machine.
b) CNF and GNF.
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)-1162

---