A E192010 Pages:3

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION(R&S), DECEMBER 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 Define nondeterministic finite automata(NFA). Draw the NFA for the language 3
L={a" b™|n, m>=1}
2 Convert the following NFA to DFA. 3

3 Write regular expression for the language L={ 1" 0™ [> =], m>=0} 3
4 Differentiate Moore machine from Mealy machine. Write the tuple 3
representation for both machines.
PART 13

Answer any two full questions, each carries 9 marks.

5 9) 4112 the notation for the language defined by a DFA. Write a string belong to 3
the language L* if L={0,1}°
b) Construct NFA without € — transitions from the following NFA. M=({ qo, qi. 6
02]. {a, 0, ०), 0, ‏,وو‎ (५21) and 6(qo, a) = {qo}, 0(५०, 0) = {qi}, ०(१०., ०) = (५2)
‏ب رو)ة‎ 0 = {१०}. ०(१1 , a) = {qi}, ‏رو)ۃ‎ , 6) = (५2),
6(92, €) = {qi}, 8(02, a) = {qo}, 6(92, ௦) = {qo}.
6 93) State Myhill-Nerode Theorem.
b) Minimize the following DFA. 6

دن

*P3

|

Page lof 3