A A7009
Total Pages: 2
Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2017

Course Code: CS301
Course Name: THEORY OF COMPUTATION (CS)
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 Define Non Deterministic Finite Automata? Compare its ability with )3(
Deterministic Finite Automata in accepting languages.
2 Write the notations for the language accepted by DFA, NFA, ‏۸ء‎ (3)
3 Can we use finite state automata to evaluate 115 complement of a binary number? (3)
Design a machine to perform the same.
4 Define Two-way finite automata (3)
PART B

Answer any two full questions, each carries 9 marks.

5 9) Design a Finite state automata which accepts all strings over {0,1} with odd (5)
number of 1'5 and even number of 0’s.
b) Show the changes needed to convert the above designed automata to accepteven (4)
number of 175 and odd number of 0’s

6 2) Construct Regular grammar for the regular expression : (5)
1, = (8 + 0)*(28 + bb)(a + b)*

b) List the closure properties of Regular sets. (4)

7 State Myhill-Nerode theorem. Minimize the following DFA by table filling (9)

method using Myhill-Nerode theorem describing the steps in detail.

PART C
Answer all questions, each carries 3 marks.
8 Which Normal Form representation of CFG will you prefer in converting CFG to (3)
NPDA? Why?

Page 1 of 2