Theoretical computer science

Automata Notes

Hand written Notes For Automata

Automata Theory ::::Solutions to Selected Exercises

Solutions for Chapter 2
Solutions for Chapter 3
Solutions for Chapter 4
Solutions for Chapter 5
Solutions for Chapter 6
Solutions for Chapter 7
Solutions for Chapter 8
Solutions for Chapter 9
Solutions for Chapter 10
Solutions for Chapter 11

Theory of Computation Syllabus

MS-11 Theory of Computation
                                                  Unit – I
Formal Languages, Need for formal computational models, Non-computability and examples of non-
computable problems, diagonal argument and Russel's paradox, Chomsky hierarchy of formal languages,
Regular languages, Regular sets, regular grammars, computable and non-computable problems.
                                                  Unit – II
Deterministic and Non-Deterministic finite automata, equivalence of deterministic and non-deterministic
finite automata, Kleen's characterization theory for sets accepted by finite automata, finite state machines and
their relations to combinatorial switching circuits, complexity, State equivalence and state minimization of
finite automata, pumping lemma, Algebra decomposition and structure theory.
                                                   Unit – III
Context Free Grammers, Chomsky & Greibiech normal form theorems, Self embedding, Equivalence of
context free languages and sets accepted by non-deterministic push down store automata, pushdown
automata, closure properties of context free languages, Ambiguity, Ambiguous grammars, Parsing: Early's,
Cook-Kasami-Young, Tomito's, top-down and bottom-up methods, Restrictions of push-down automata.
                                                 Unit – IV
Linear bounded automata (LBA): Power of LBA, closure properties
Turing machine (TM): one-tape, Multitape Turing machines and related formalism for recognition, Time and
space complexity in terms of TM, Construction of TM for various problems, Unsolvability of the halting
problem, reduction of post correspondence problem to the halting problem, Undecidable properties of
grammars. Recursive and recursively enumerable language.

Text Books
1 Kamla kirtheivshan & Rama R, Automata theory & Computation, PEARSON, 1/e
2 Peter Linz, An introduction to formal language & automata, Jones & Bartlete pub. 5/e

Reference Books:
1. Hopcroft,J.E.&Ullman,J.D. Formal languages and their relation to Automata, Addison-Wasley
2. E.V.Krishnamurthy, Introductory Theory of Computer Science Ease-West press Pvt. Ltd.
3. Salomma, A.K. Formal languages, Academic press.
4. Lewis, H.R.& Papadimitrious, C.H. Elements of the Theory of Computation.PHI.
5. Zoha Mauna, Mathematical Theory of Computation, Wiley Inter-science.

Introduction to Automata Theory, Languages, and Computation

Theory of Computation Best Book

Theory of Computation Books

Advanced Complexity Theory
by Daniel Spielman, 2001, PDF

Algorithmic Randomness and Complexity
by R. G. Downey, D. R. Hirschfeldt, 2010, 629 pages, 4MB, PDF

Bayesian Computational Methods
by Christian P. Robert, 2010, 59 pp, 3.7MB, PDF

Cellular Automata
edited by S. Bandini, B. Chopard, M. Tomassini, 2002, 379 pp, 8.3MB, PDF

Cellular Automata
Wikibooks, 2010

Cellular Automata And Complexity: Collected Papers
by Stephen Wolfram, 1994

Cellular Automata: Simplicity Behind Complexity
edited by Alejandro Salcido, 2011, 566 pages, 31MB, PDF

Combinatorial Optimization: Exact and Approximate Algorithms
by Luca Trevisan, 2011, 139 pages, 830KB, PDF

Communication Complexity
by Domotor Palvolgyi, 2005, 39 pages, 380KB, PDF

Complexity
by Rajesh R. Parwani, 2002

Complexity Theory by Johan Hastad, 2008, 130 pages, 0.7MB, PDF

Computability and Complexity
Wikibooks, 2010

Computability and Complexity from a Programming Perspective
by Neil D. Jones, 1997, 485 pages, 1.7MB, PDF

Computability and Randomness
by Andre Nies, 2008, 447 pages, 2.6MB, PDF

Computability Theory
by Wilfried Sieg, 2006, 125 pp, 1.9MB, PDF

Computational Complexity: A Modern Approach
by Sanjeev Arora, Boaz Barak, 2008, 489 pages, 4.4MB, PDF

Computational Modeling and Complexity Science
by Allen Downey, 2008, 97 pages, 1.4MB, PDF

Finite-state Automata in Java
by Bradley Kjell

From Complexity to Creativity
by Ben Goertzel, 1996

From Philosophy to Program Size
by G. J. Chaitin, 2003, 54 pages, PS/PDF

Handbook of Quantum Information
Quantiki, 2013, online html

Introduction to Complexity Theory
by Oded Goldreich, 1999, 375 pages, 2.3MB, PDF

Introduction to Computational Complexity
by Martin Tompa, 1991, 85 pages, 1MB, PDF

Introduction to Quantum Algorithms for Physics and Chemistry
by Man-Hong Yung, et al. 2012, 44 pp, 2MB, PDF

Introduction to Quantum Cellular Automata
by B. Aoun, M. Tarifi, 2004, 46 pages, 330KB, PDF

An Introduction to Quantum Computing using Cavity QED concepts
by Zachary Burell, 2012, 53 pp, 260KB, PDF

An Introduction to the Theory of Computation
by Eitan Gurari, 1989, 314 pages, 3.2MB, ZIP/HTML

Lecture Notes on Algorithm Analysis and Computational Complexity
by Ian Parberry, 119 pages, 1.9MB, PDF

Lecture Notes on Computational Complexity
by Luca Trevisan, 2004, 171 pages, 0.9MB, PDF

Logic for Computer Scientists
by Uli Furbach, 2010

Mathematical Foundations of Automata Theory
by Jean-Eric Pin, 2012, 310 pp, 1.9MB, PDF

Notes on Automata, Logics, Games and Algebra
by K Narayan Kumar, 2007, PDF

P, NP, and NP-Completeness: The Basics of Complexity Theory
by Oded Goldreich, 2010, 190pp, 1.9MB, PS

Physics, Topology, Logic and Computation: A Rosetta Stone
by John C. Baez, Mike Stay, 2009, 73 pages, 780KB, PDF

Quantum Computation
by John Watrous, 2006, 139 pages, 660KB, PDF

Quantum Walks: A Comprehensive Review
by Salvador E. Venegas-Andraca, 2012, 88 pp, 1.5MB, PDF

Recursion Theory
by Frank Stephan, 2009, 125 pp, 610KB, PDF

Rule-based Computation and Deduction
by Helene Kirchner, Pierre-Etienne Moreau, 2001, 100 pp, 870KB, PDF

Think Complexity: Complexity Science and Computational Modeling
by Allen B. Downey, 2012, 146 pp, 1.2MB, PDF

Tree Automata Techniques and Applications
by H. Comon, M. Dauchet, R. Gilleron, 2008, 262 pages, 2MB, PDF

Theory of Automata Materials

 

CSL 705: Theory of Computation