Download PTU B.Tech 2020 March CSE-IT 7th and 8th Sem BTIT 904 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 BTIT 904 Theory Of Computation Previous Question Paper

1 | M-71983 (S2)-2364
Roll No. Total No. of Pages : 02
Total No. of Questions : 09
B.Tech (Information Technology) (Sem.?7)
THEORY OF COMPUTATION
Subject Code : BTIT-904
M.Code : 71983
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS 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
1. Write briefly :
a) Moore Machine
b) DFA
c) TM
d) Grammar
e) Yield
f) Instantaneous Description
g) Right context
h) UNIT Production
i) Parse tree
j) CNF and GNF
FirstRanker.com - FirstRanker's Choice
1 | M-71983 (S2)-2364
Roll No. Total No. of Pages : 02
Total No. of Questions : 09
B.Tech (Information Technology) (Sem.?7)
THEORY OF COMPUTATION
Subject Code : BTIT-904
M.Code : 71983
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS 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
1. Write briefly :
a) Moore Machine
b) DFA
c) TM
d) Grammar
e) Yield
f) Instantaneous Description
g) Right context
h) UNIT Production
i) Parse tree
j) CNF and GNF
2 | M-71983 (S2)-2364
SECTION-B
2. Construct a finite automata equivalent to the regular expression :
(0+1 )* (00 + 11 ) (0 + 1 )*
3. Explain the concept of ambiguity with the help of example.
4. Construct a Moore machine equivalent to the Mealy machine M defined by following
table :
Present State Next State
a = 0 a = 1
State Output State Output
?q
1
q
1
0 q
2
1
q
2
q
4
0 q
4
0
q
3
q
2
0 q
3
1
q
4
q
3
1 q
1
1
5. State and Describe pumping lemma
6. Find a reduced grammar equivalent to the given grammar
S ? AC | B, A ? a, C ? c | BC, E ? aA | e

SECTION-C
7. Design PDA for {ww
T
| w={a,b}*}
8. Give rules of converting CFG into PDA.
9. Describe any two representation of TM.



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.

FirstRanker.com - FirstRanker's Choice