Automata and Formal Languages (CS 250)

Outline

25 sections

1. 01Course Intro & Syllabus
2. 02Section 1: Course Introduction & Overview of Computation
3. 03Section 2: Math Notions, Theorems, and Proofs
4. 04Section 3: Deterministic Finite Automata
5. 05Section 4: Nondeterministic Finite Automata
6. 06Section 5: Regular Expressions and Equivalence
7. 07Section 6: Nonregular Languages and the Pumping Lemma
8. 08Section 7: Context-Free Grammars
9. 09Section 8: Pushdown Automata
10. 10Section 9: Non-Context-Free Languages
11. 11Section 10: Deterministic Context-Free Languages
12. 12Midterm Exam
13. 13Section 11: Turing Machines
14. 14Section 12: Variants of Turing Machines & The Definition of Algorithm
15. 15Section 13: Decidable Languages
16. 16Section 14: Undecidability and the Halting Problem
17. 17Section 15: Undecidable Problems from Language Theory
18. 18Section 16: Computation Histories and Mapping Reducibility
19. 19Section 17: Measuring Complexity and The Class P
20. 20Section 18: The Class NP
21. 21Section 19: NP-Completeness and the Cook-Levin Theorem
22. 22Section 20: Additional NP-Complete Problems
23. 23Section 21: Space Complexity and Savitch's Theorem
24. 24Section 22: PSPACE-Completeness and The Complexity Universe
25. 25Final Exam

Course facts

At a glance

Course

Automata and Formal Languages (CS 250)

Course code

CS 250

Track

Computing & engineering

Price

$40 $64.99

Lessons

180

Total runtime

20:49:31

Delivery

100% online, self-paced

Language

English

On completion

Certificate of completion — a non-degree credential