Theory of Computation Hand Note

Description

Theory of Computation Hand Note

Page Length : 273

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