۸ 0000002 Pages: 2

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Fifth Semester B.Tech Degree Regular and Supplementary Examination December 2020

Course Code: 01
Course Name: THEORY OF COMPUTATION

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks. Marks
1 Design a DFA to accept the set of binary strings ending with 0 (3)
2 Show the formal definition of the transition relation in an e-NFA. Illustrate how (൫)

a transition is performed by an ‏.۸۰ء‎

3 List two differences between Moore and Mealy Machines. Give a Mealy (3)
machine with the minimum possible number of states that outputs the one’s
complement of a given binary string.

4 Give a regular grammar for the language {w ‏ء‎ {a, b}* | w has even number of )3(
‘a’s and even number of ‘b’s}

PART B
Answer any two full questions, each carries 9 marks.

5 ஐ Design a DFA for the language {1 € {0, 1)* | w, when considered as aninteger, (6)
is a multiple of 3}.
b) Design a DFA for the language (ம € {a, b}* | w did not contain ‘aab’ asa (3)
substring }.
6 9) Find an e-NFA for the language L(a(a+b)*b) employing the rules for regular (3)
expression to ¢-NFA conversion.
b) Convert the above e-NFA into an equivalent DFA, clearly showing the steps of (6)
the standard procedure for the same.
7 Find a DFA and a regular expression for the language {w € {a, b}* | whas odd (9)
number of ‘a’s}.
PART ^
Answer all questions, each carries 3 marks.
8 When a Grammar is said to be ambiguous? Show that the grammar with (3)
productions P= {2 -> E+ 8 | ‏ع‎ * 8 | (5) | 6 for simple arithmetic expressions,

is ambiguous.

Page 1 of 2