CS9253 THEORY OF COMPUTATION
UNIT I AUTOMATA
Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata –
Deterministic Finite Automata – No deterministic Finite Automata – Finite Automata with Epsilon
Transitions.
UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular Expression – 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 INDECIDABILITY
A Language That Is Not Recursive Enumerable – An Undecidable Problem that Is RE –
Undecidable Problems about TM – Post’s Correspondence Problem, The Class P And NP.
TEXT BOOKS:
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.
UNIT I AUTOMATA
Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata –
Deterministic Finite Automata – No deterministic Finite Automata – Finite Automata with Epsilon
Transitions.
UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular Expression – 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 INDECIDABILITY
A Language That Is Not Recursive Enumerable – An Undecidable Problem that Is RE –
Undecidable Problems about TM – Post’s Correspondence Problem, The Class P And NP.
TEXT BOOKS:
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.
No comments:
Post a Comment