ച

A R5921 (85೫12003862
क्छ pie:
‏ا‎ 7 /

as 2 2 5

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2018
Course Code: CS301
Course Name: THEORY OF COMPUTATION (CS)

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks. Marks
1 What is the regular expression for the DFA (3)

2 Compare the transition functions of NFA and DFA. (3)
3 Explain in English language the language accepted by the DFA in Question 1. (3)
4 What is a Moore machine? How is it different from mealy machine? (3)
PART 13
Answer any two full questions, each carries 9 marks.

5 9) Convert the NFA to DFA ۲ (4.5)

b) Prove the equivalence of regular expression and Finite state automata. (4.5)
6 a) Prove the equivalence of NFA and e-NFA. (4.5)

b) Draw a six state DFA which can be minimized 10 a three state DFA where set (4.5)

of input symbols is {a, b, c}. Draw both the DFAs. Assume whatever is

required.
7 9) Prove the equivalence of NFA and DFA. (4.5)
b) What is Myhill Nerode Theorem? (4.5)
PART ட
Answer all questions, each carries 3 marks.
8 What is a derivation tree? (3)

Page 1 2