CS8501 – NOTES & QP
| NOTES | CLICK HERE |
| SEMESTER QP | CLICK HERE |
CS8501 – SYLLABUS
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.