Completed
7. Decision Problems for Automata and Grammars
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Theory of Computation, Fall 2020
Automatically move to the next video in the Classroom when playback concludes
- 1 1. Introduction, Finite Automata, Regular Expressions
- 2 2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
- 3 3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
- 4 4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
- 5 5. CF Pumping Lemma, Turing Machines
- 6 6. TM Variants, Church-Turing Thesis
- 7 7. Decision Problems for Automata and Grammars
- 8 8. Undecidability
- 9 9. Reducibility
- 10 10. Computation History Method
- 11 11. Recursion Theorem and Logic
- 12 12. Time Complexity
- 13 14. P and NP, SAT, Poly-Time Reducibility
- 14 15. NP-Completeness
- 15 16. Cook-Levin Theorem
- 16 17. Space Complexity, PSPACE, Savitch's Theorem
- 17 18. PSPACE-Completeness
- 18 19. Games, Generalized Geography
- 19 20. L and NL, NL = coNL
- 20 21. Hierarchy Theorems
- 21 22. Provably Intractable Problems, Oracles
- 22 23. Probabilistic Computation, BPP
- 23 24. Probabilistic Computation (cont.)
- 24 25. Interactive Proof Systems, IP
- 25 26. coNP is a subset of IP
