CS8501 Theory of Computation Previous Year Question Paper Download
· 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
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.
CS8501 Theory of Computation Previous Year Question Paper for Regulation 2017 question paper Download
- CS8501 Theory of Computation Apr/May 2019 Question Paper
- CS8501 Theory of Computation Nov/Dec 2019 Question Paper
MA8551 Algebra and Number Theory Previous Year Question Paper Download