4 00000CS301121901 Pages: 3

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Fifth semester B.Tech degree examinations (S) September 2020

Course Code: 01
Course Name: THEORY OF COMPUTATION

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries3 marks. Marks
1 Formally define extended delta for an NFA. Show the processing of input (3)

w = 0101 for the following NFA.
→−→−→
0 1
0,1

2 Differentiate between the transition function in DFA, NFA and e-NFA (3)
9 Design a Moore machine to determine the residue of mod 2 of the input treated (3)
as a binary string.
4 Give a regular expression for the set of all strings not containing 101 as ೩ (3)
substring
PART B
Answer any two full questions, each carries 9 marks.
5 a) Convert the following NFA to DFA and describe the language it accepts. (5)
M = ({P,Q,R,S,T}, {0,1}, 6,7, {S,T}) and 6 is given as:

0 ]
P | {P,Q}

© | (1.5)

R | ஐய)

S |- |

7 [- ಜ್‌

0) Prove that ^ A language L is accepted by some e-NFA if and only if Lis (4)
accepted by some NFA”