# CS8501 THEORY OF COMPUTATION NOTES 2017 REGULATION

In this post we have posted some notes on CS8501 THEORY OF COMPUTATION of PROFESSIONAL CORE for ANNA UNIVERSITY AFFILIATED COLLEGES STUDENTS.
Here We have listed the the notes whichever we could collect for CS8501 THEORY OF COMPUTATION subject, We think that it will be helpful for your exam preparation.

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

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

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

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

Normal Forms for CFG â€“ Pumping Lemma for CFL â€“ Closure Properties of CFL â€“ Turing Machines â€“ Programming Techniques for TM.

#### UNIT V UNDECIDABILITY

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

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

### CS8501 THEORY OF COMPUTATION NOTES

If you have any queries or comments on this post, kindly contact us through contact form or telegram