A 06000CS301122001 Pages: 2

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Fifth Semester B.Tech Degree (S,FE) Examination January 2022 (2015 Scheme)

Course Code: CS301
Course Name: THEORY OF COMPUTATION
Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks. Marks
1 Write a regular grammar for generating the language L = {a"b"| m, n 0] (3)
2 Design a DFA for L = {x in {a,b} | x contains even number of a’s} (3)
3 Explain Mealy machine. (3)
4 Illustrate the working of 2-way Finite State State Automata (3)
PART 8
Answer any two full questions, each carries 9 marks.
5 a) Prove that the language accepted by NFA and DFA are same (6)
b) Define e-closure of a state in an e-NFA. Give an example. (3)

6 a) Convert the following NFA to DFA using subset construction where (0 is the (6)

initial state and 01 is the final state.

மி | | | |

)40( | )60.41( | من

*ql a ()

b) Design an e-NFA for the language L = {x in {0,1 } | x contains any number of (3)
Os followed by any number of 1s }
7 a) With the help of an example explain Thompsons Construction (Regular (5)
Expression to NFA)
b) Write regular expressions for the following languages (4)
i) L={xin {a,b} | x starts with a }

ii) L= {xin {a,b} | ೫ contains a as third character}

Page 1 of 2