CS8501 - THEORY OF COMPUTATION (Syllabus) 2017-regulation Anna University

CS8501 - THEORY OF COMPUTATION (Syllabus) 2017-regulation Anna University

CS8501

THEORY OF COMPUTATION

 LPTC
3003

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.
Previous
Next

Comments

Post a Comment

Popular posts from this blog

CS3491 Syllabus - Artificial Intelligence And Machine Learning - 2021 Regulation Anna University

CS3491 Syllabus - Artificial Intelligence And Machine Learning - 2021 Regulation Anna University CS3491 ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING  LTPC 3024 COURSE OBJECTIVES: • The main objectives of this course are to: • Study about uninformed and Heuristic search techniques. • Learn techniques for reasoning under uncertainty • Introduce Machine Learning and supervised learning algorithms • Study about ensembling and unsupervised learning algorithms • Learn the basics of deep learning using neural networks We're excited to announce the launch of our new website! Visit NameWheelSpinner.com to explore its features and benefits. UNIT I PROBLEM SOLVING 9 Introduction to AI - AI Applications - Problem solving agents – search algorithms – uninformed
Read more

BE3251 - Basic Electrical and Electronics Engineering (Syllabus) 2021-regulation Anna University

BE3251 - Basic Electrical and Electronics Engineering (Syllabus) 2021-regulation Anna University BE3251 Basic Electrical and Electronics Engineering  LPTC 3003 COURSE OBJECTIVES: • To introduce the basics of electric circuits and analysis • To impart knowledge in the basics of working principles and application of electrical machines • To introduce analog devices and their characteristics • To educate on the fundamental concepts of digital electronics • To introduce the functional elements and working of measuring instruments We're excited to announce the launch of our new website! Visit NameWheelSpinner.com to explore its features and benefits. UNIT I ELECTRICAL CIRCUITS 9 DC Circuits: Circuit Components: Conductor, Resistor, Inductor, Capacitor – Ohm’s Law - Kirchhoff’s Laws –Independent and Dependent Sources – Simple problems- Nodal Analysis, Mesh analysis with Independent sources only (Steady state) Introd
Read more

CS3401 Syllabus - Algorithms - 2021 Regulation Anna University

CS3401 Syllabus - Algorithms - 2021 Regulation Anna University CS3401 ALGORITHMS  LTPC 3024 COURSE OBJECTIVES: • To understand and apply the algorithm analysis techniques on searching and sorting algorithms • To critically analyze the efficiency of graph algorithms • To understand different algorithm design techniques • To solve programming problems using state space tree • To understand the concepts behind NP Completeness, Approximation algorithms and randomized algorithms. We're excited to announce the launch of our new website! Visit NameWheelSpinner.com to explore its features and benefits. UNIT I INTRODUCTION 9 Algorithm analysis: Time and space complexity - Asymptotic Notations and its properties Best case, Worst case and average case analys
Read more