Theory of Computation detail syllabus for Computer Science & Engineering (Cse), 2017 regulation is taken from Anna University official website and presented for students of Anna University. The details of the course are: course code (CS8501), Category (PC), Contact Periods/week (3), Teaching hours/week (3), Practical Hours/week (0). The total course credits are given in combined syllabus.
For all other cse 5th sem syllabus for be 2017 regulation anna univ you can visit Cse 5th Sem syllabus for BE 2017 regulation Anna Univ Subjects. The detail syllabus for theory of computation is as follows.”
Course Objective:
- 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
For complete syllabus and results, class timetable and more pls download iStudy. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.
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
For complete syllabus and results, class timetable and more pls download iStudy. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.
Unit V
Undecidability
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Posts Correspondence Problem, The Class P and NP.
Course Outcome:
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 Books:
- J.E.Hopcroft, R.Motwani and J.D Ullman, Introduction to Automata Theory, Languages and Computations, Second Edition, Pearson Education, 2003.
References:
- H.R.Lewis and C.H.Papadimitriou, Elements of the theory of Computation, Second Edition, PHI, 2003.
- J.Martin, Introduction to Languages and the Theory of Computation, Third Edition, TMH, 2003.
- Micheal Sipser, Introduction of the Theory and Computation, Thomson Brokecole, 1997.
For detail syllabus of all other subjects of BE Cse, 2017 regulation do visit Cse 5th Sem syllabus for 2017 Regulation.
Dont forget to download iStudy for latest syllabus and results, class timetable and more.