0
3472

# CS8501- THEORY OF COMPUTATION Syllabus 2017 Regulation

THEORY OF COMPUTATION CS8501- THEORY OF COMPUTATION Syllabus 2017 Regulation Syllabus 2017 Regulation

Â CS8501Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  THEORY OF COMPUTATIONÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â L T P CÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â 3 0 0 3

OBJECTIVES:

• To understand the language hierarchy
• To construct automata for any given pattern and find its equivalent regular expressions
• To design a context free grammar for any given language
• To understand Turing machines and their capability
• To understand undecidable problems and NP class problems

## UNIT I AUTOMATA FUNDAMENTALSÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  9

Introduction to formal proof â€“ Additional forms of Proof â€“ Inductive Proofs â€“Finite Automata â€“ Deterministic Finite Automata â€“ Non-deterministic Finite Automata â€“ Finite Automata with Epsilon Transitions

## UNIT II REGULAR EXPRESSIONS AND LANGUAGESÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  9

Regular Expressions â€“ FA and Regular Expressions â€“ Proving Languages not to be regular â€“ Closure Properties of Regular Languages â€“ Equivalence and Minimization of Automata.

## UNIT III CONTEXT FREE GRAMMAR AND LANGUAGESÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â 9

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.

## UNIT 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.

## UNIT V UNDECIDABILITYÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â 9

Non Recursive Enumerable (RE) Language â€“ Undecidable Problem with RE â€“ Undecidable Problems about TM â€“ Postâ€˜s Correspondence Problem, The Class P and NP.

Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  TOTAL :45 PERIODS

OUTCOMES:

Upon completion of the course, the students will be able to:

• Construct automata, regular expression for any pattern.
• Write Context free grammar for any construct.
• Design Turing machines for any language.
• Propose computation solutions using Turing machines.
• Derive whether a problem is decidable or not.

TEXT BOOK:

1. J.E.Hopcroft, R.Motwani and J.D Ullman, â€•Introduction to Automata Theory, Languages and Computationsâ€–, Second Edition, Pearson Education, 2003.

REFERENCES:

1. H.R.Lewis and C.H.Papadimitriou, â€•Elements of the theory of Computation, Second Edition, PHI, 2003.
2. J.Martin, â€•Introduction to Languages and the Theory of Computation, Third Edition, TMH, 2003.
3. Micheal Sipser, â€•Introduction of the Theory and Computation, Thomson Brokecole, 1997.