A E1107 Pages: 3

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION(S), MAY 2019
Course Code: CS301
Course Name: THEORY OF COMPUTATION

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks. Marks
1 What is a Finite state automata? (3)
2 Construct DFA for the language 101° (3)
3 Give the regular expression for the language: strings of ‘a’ and ‘b’ (3)

containing at least two ‘b’.

4 What is a two-way finite automata? (3)
PART छ
Answer any two full questions, each carries 9 marks.
5 9) Find the regular expression corresponding to the language of the (4.5)
given D 6 A ்‌

b) Prove the equivalence of NFA and ‏۸۰ء‎ (4.5)
6 a) Convert the e-NFA to NFA. (4.5)

b) Prove the equivalence of regular expression and finite state automata (4.5)

7 8) Compare the transition functions of DFA, NFA and e-NFA. (4.5)

Page 1 of 3