Download PTU B.Tech 2020 March CSE-IT 7th and 8th Sem BTCS 702 Theory Of Computation Question Paper

Download PTU (I.K. Gujral Punjab Technical University Jalandhar (IKGPTU) ) BE/BTech CSE/IT (Computer Science And Engineering/ Information Technology) 2020 March 7th and 8th Sem BTCS 702 Theory Of Computation Previous Question Paper

1 | M-71894 (S2)-208
Roll No. Total No. of Pages : 02
Total No. of Questions : 18
B.Tech.(CSE) (2012 to 2017) (Sem.?7,8)
THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60
INSTRUCTION TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt ANY FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students
have to attempt ANY TWO questions.

SECTION-A
Answer Briefly :
Q1. Define Mealy and Moore machines.
Q2. Define the term acceptability of a string.
Q3. Define pumping lemma for regular sets.
Q4. Differentiate between left linear and right linear regular grammar.
Q5. Define yield and ambiguity in CFG.
Q6. Give example CNF and GNF productions.
Q7. Differentiate between deterministic and non-deterministic PDA.
Q8. Give rules for converting CFG to PDA.
Q9. Give instantaneous description of Turing machine.
Q10. What do you mean by halting problem of TM?

FirstRanker.com - FirstRanker's Choice
1 | M-71894 (S2)-208
Roll No. Total No. of Pages : 02
Total No. of Questions : 18
B.Tech.(CSE) (2012 to 2017) (Sem.?7,8)
THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60
INSTRUCTION TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt ANY FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students
have to attempt ANY TWO questions.

SECTION-A
Answer Briefly :
Q1. Define Mealy and Moore machines.
Q2. Define the term acceptability of a string.
Q3. Define pumping lemma for regular sets.
Q4. Differentiate between left linear and right linear regular grammar.
Q5. Define yield and ambiguity in CFG.
Q6. Give example CNF and GNF productions.
Q7. Differentiate between deterministic and non-deterministic PDA.
Q8. Give rules for converting CFG to PDA.
Q9. Give instantaneous description of Turing machine.
Q10. What do you mean by halting problem of TM?

2 | M-71894 (S2)-208
SECTION-B
Q11. Construct a DFA equivalent to :

? ? ? ? ? ? ? ?
0, 1, 2, 3, 0, 3,
, 0,1 , , M q q q q q q ? ? , where ? is given by following state table :
State/ ? a b
? q
0
q
0
, q
1
q
0

q
1
q
2
q
1

q
2

q
3
q
3



q
2

Q12. Explain in detail the Chomsky classification of languages.
Q13. Define regular sets and write its closure properties.
Q14. Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular expression
Describe any two representation of TM.
Q15. Find a reduced grammar equivalent to the given grammar.
S AC | B,A a,C c | BC,E aA | e ? ? ? ?

SECTION-C
Q16. Find a grammar in GNF equivalent to the grammar
E ? E + T | T T ? T * F | F F ? (E) | a
Q17. Design Turing Machine of {0
n
1
n
| n ? ?1}.
Q18. Describe PDA with its representations. Also write rules of converting PDA to CFG.

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.
q
3
FirstRanker.com - FirstRanker's Choice