This course on Finite Automata in Theoretical Computer Science aims to teach students the following:
- Understanding Deterministic Finite Automata (DFAs) and Regular Languages
- Exploring the anatomy of DFAs and how to compute with them
- Learning the formal definition of DFAs and practicing DFA construction
- Proving whether a language is regular or not using Union Theorem
The teaching method includes lectures, examples, problem-solving, and practice sessions. This course is intended for students and professionals interested in theoretical computer science and computational theory.
Great Ideas in Theoretical Computer Science: Finite Automata
Overview
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
