About Lesson
12.1) BNF, Languages, grammars
12.2) DFA and NDFA, regular expressions, regular grammars
12.3) Closure, homomorphism
12.4) Pigeonhole principle, pumping lemma
12.5) CFGs, Parsing and ambiguity, Pushdown automata, NPDAs & CFGs
12.6) Pumping lemma
12.7) Turing machines
12.8 Recursively enumerable languages Unrestricted grammars
12.9 The Chomsky hierarchy, Undecidable problems, Church’s Thesis
12.10 Complexity Theory, P and NP
