Great Ideas in Theoretical Computer Science: Finite Automata
Offered By: Ryan O'Donnell via YouTube
Course Description
Overview
Explore the fundamentals of finite automata and regular languages in this comprehensive lecture from CMU's "Great Ideas in Theoretical Computer Science" course. Delve into deterministic finite automata (DFAs), their anatomy, and computational processes. Learn about regular languages, string notation, and problem representation in theoretical computer science. Practice DFA construction and discover techniques for proving whether a language is regular or not. Gain insights into the Union Theorem and its applications in automata theory.
Syllabus
15-251: Great Theoretical ideas in Computer Science Lecture 4
Inspirational quotation #2
Example problem 2 PALINDROME
Example problem 3
String notation
Representing problems
What is computation? What is an algorithm?
Deterministic Finite Automata (DFAs)
Anatomy of a DFA
Computing with DFAs
Formal definition of DFAs
DFA-construction practice
Regular Languages
Proving a language L is not regular
Union Theorem
Taught by
Ryan O'Donnell
Related Courses
Automata TheoryStanford University via edX Theory of Computation
Indian Institute of Technology Kanpur via Swayam Introduction to Automata, Languages and Computation
Indian Institute of Technology, Kharagpur via Swayam Математика в тестировании дискретных систем
Tomsk State University via Coursera Theory of Computation
NPTEL via YouTube