Theory of Computation

This book offers a thorough introduction to the concepts of Theory of Computation and is designed as per the latest Anna University Syllabus Regulations 2017. This book is also meant for students of various other related disciplines for both UG and PG courses.

Author(s): Dr. M. Shyamala Devi

UNIT – I FINITE AUTOMATA
Chapter 1 – Finite State Systems
Chapter 2 – Regular Languages and Expressions
UNIT – II GRAMMARS
Chapter 3 – Context Free Grammar
Chapter 4 – Simplication of Context Free Grammar
UNIT – III PUSHDOWN AUTOMATA
Chapter 5 – PDA and CFG
Chapter 6 – Pumping Lemma for Context Free Language
UNIT – IV TURING MACHINES
Chapter 7 – Construction of Turing Machine
Chapter 8 – Problems about Turing Machine
UNIT – V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS
Chapter 9 – Recursive Functions
Chapter 10 – Measuring and Classifying Complexity

1. Student-friendly, easy to understand text and a step-by-step approach to problems.
2. Introduction to basic mathematical notations and techniques, deductive, reduction and inductive proofs, etc.
3. Finite Automata Theory has been given adequate coverage with its types and conversions.
4. Exhaustive coverage of Context Free Grammars and Pushdown Automata and its construction.
5. Construction of Turing Machines and the programming techniques of Turing Machines are covered with the multiple track, subroutines, storage in finite control with suitable examples.
6. Includes coverage of Unsolvable problems, Undecidability along with Post correspondence problems and Class P, NP with examples.
7. Concepts of measuring and classifying complexity is rendered clear coverage with theorems.

ISBN : 9788182094635
Price : 425.00
Choose Quantity :
  • Published: 08 July 2019
  • Edition: 1
  • ISBN: 9788182094635
  • Availability: In Stock
  • Pages: 578