Great Ideas in Theoretical Computer Science: Finite Automata

This lecture introduces deterministic finite automata as mathematical models of computation and uses them to study regular languages. It includes construction practice and a proof that some languages cannot be recognized by a DFA.

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