A A5810 Pages: 2

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION, APRIL 2018

Course Code: 1
Course Name: THEORY OF COMPUTATION (CS)
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks Marks

1 Construct regular expression for the language that consists of all strings ending (3)

with 00. Assume (0, 1).
2 Design non deterministic automata (without ‏ع‎ moves) for the regular language (3)

that consist of all strings with at least two consecutive 0’s. Assume ೫ = {0, 1}.

3 Define regular grammar with suitable example. (3)
4 List some of the applications of automata theory. (3)
PART B
Answer any two full questions, each carries 9 marks
5 Prove the equivalence of non deterministic finite automata and deterministic (9)

finite automata.
6 Prove the equivalence of non deterministic finite automata with ‏ع‎ moves and (9)
regular expressions.

7 a) Construct non deterministic finite automata (with ‏ع‎ moves) for regular (4)
expression (0+1 1 1.

b) Compare and contrast Moore and Mealy machines. (Justify with diagrams). (5)
PART C
Answer all questions, each carries 3 marks
8 Construct context free grammar for L= {wew" | w in (atb)*}, Reverse of wis (3)
denoted as फा,
9 List conditions for symbols to become useful symbols in context free grammar. (3)
10 List conditions required for push down automata to qualify as deterministic push (3)
down automata.
11 List closure properties of context free language. (3)
PART D

Answer any two full questions, each carries 9 marks

12 Do the following: (9)
i) Construct push down automata with empty stack as final condition for Context
free language, L= { wew"| w in (a+b)*} .Reverse of w is denoted as फर,
ii) Describe all instantaneous descriptions from initial ID
(start state 40004, initial stack symbol) |--* to final ID (state, ‏بع‎ 8) with respect to
constructed push down automata.

Page 1 of 2