In these “Theory of Computation Notes ”, the TOC (Theory of Computation) can be separated into three theories like computability theory, complexity theory, as well as automata theory. The topics we will cover in these Theory of Computation such as finite automaton, pushdown automaton, and Turing machine; and their relationships with formal languages.

We have provided multiple complete Theory of Computation Notes for any university student of BCA, MCA, B.Sc, B.Tech CSE, M.Tech branch to increase more knowledge about the subject.

Cover Topic :

• Introduction
• BNF
• Languages and grammars (most important!)
• DFAs and their implementation
• NDFAs and their implementation
• DFAs = NDFAs
• Regular expressions
• Regular expressions denote regular languages
• Regular grammars
• Closure, homomorphism
• Pigeonhole principle, pumping lemma (difficult)
• CFGs
• Parsing and ambiguity
• Pushdown automata
• NPDAs & CFGs
• A pumping lemma for cfgs (still difficult)
• Turing machines
• Universal Turing Machines and LBAs
• Recursively enumerable languages
• Unrestricted grammars
• The Chomsky hierarchy
• Undecidable problems
• Church’s Thesis
• Complexity Theory, P and NP