Anna University , Chennai

Question Paper Code : 51348

B.E./B.Tech. DEGREE EXAMINATIONx MAY/JUNE 2014.

Fifth Semester

Computer Science and Engineering

CS 2303/CS 53/ 10144 CS 504 — THEORY OF COMPUTATION

(Common to Seventh Semester Information Technology)

(Regulation 2008/2010)

(Common to PTCS 2303 — Theory of computation for B.E. (Part-Time)

Fifth Semester Computer Science and Engineering — Regulation 2009)

Time : Three hours

Maximum : 100 marks

Answer ALL questions.

PART A — (10 x 2 20 marks)

1.What is a finite automaton?

2.Enumerate the difference between DFA and NFA.

3.Construct a finite automaton for the regular expression 1*

4.Mention the closure properties of regular languages.

5.Construct a CFG for the language of palindrome strings over (a, b).

6.What do you say a grammar is ambiguous?

7.State pumping Lemma for context free languages.

8.Define a turing machine.

9. When a language is said to be recursively enumerable?

10.Define the classes P and NP.

For Part B Questions, Attachment the Question Paper.

Full Name : Dhilip Prabakaran

College Name : Dhanalakshmi College of Engineering

Department : Computer Science and Engineering

Semester : 5

Subject Code : CS2303

Subject Name : Theory of Computation

Study Material Description : Question Paper of CS2303 Theory of Computation May June 2014.

Attachment :

TOC MJ14 VP.pdf (Size: 2.21 MB / Downloads: 8,246)