CS2303-THEORY OF COMPUTATION-ANNA UNIVERSITY SYLLABUS for CSE

**C**

**S2**

**3**

**0**

**3 THEORY OF COMPUTATION L T P C**

**3 1 0 4**

**UN**

**I**

**T I AUTOMATA 9**

Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite Automata (FA)
– Deterministic Finite Automata (DFA)
– Non-deterministic Finite
Automata (NFA) – Finite Automata with Epsilon transitions.

**UN**

**I**

**T II REGULAR EXPRESSIONS AND LANGUAGES 9**

Regular Expression
– FA and Regular Expressions – Proving languages not to be
regular
– Closure properties of regular
languages – Equivalence and minimization of Automata.

**UN**

**I**

**T III CONTEXT-FREE GRAMMARS AND LANGUAGES 9**

Context-Free Grammar (CFG) – Parse Trees – Ambiguity in grammars and languages –
Definition of the Pushdown automata – Languages
of a Pushdown Automata –
Equivalence of Pushdown automata and CFG– Deterministic Pushdown Automata.

**UN**

**I**

**T IV PROPERTIES OF CONTEXT-FREE LANGUAGES 9**

Normal forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing

Machines – Programming Techniques for TM.

**UN**

**I**

**T V UNDECIDABALITY 9**

A language that is not Recursively Enumerable (RE) – An undecidable problem that is RE – Undecidable problems about Turing Machine – Post’s Correspondence Problem – The classes P and NP.

**T**

**EX**

**T BOOK:**

**L: 45, T: 15, TOTAL: 60 PERIODS**

1. J.E.
Hopcroft, R.
Motwani and J.D.
Ullman, “Introduction to
Automata Theory,
Languages and Computations”, second Edition, Pearson Education, 2007.

**R**

**E**

**FERENCES:**

1. H.R. Lewis and C.H. Papadimitriou, “Elements of the theory of Computation”, Second Edition, Pearson Education, 2003.

2. Thomas A. Sudkamp,” An Introduction to the Theory of Computer Science,
Languages and Machines”, Third Edition, Pearson Education, 2007.

3. Raymond Greenlaw an H.James Hoover, “ Fundamentals of Theory of

Computation, Principles and Practice”, Morgan Kaufmann Publishers, 1998.

4. Micheal
Sipser, “Introduction of the Theory and Computation”, Thomson

Brokecole, 1997.

5. J. Martin, “Introduction to Languages and the Theory of
computation”
Third Edition, Tata Mc Graw
Hill, 2007

## 0 comments:

## Post a Comment