YoVDO

Great Ideas in Theoretical Computer Science: Finite Automata

Offered By: Ryan O'Donnell via YouTube

Tags

Automata Theory Courses Finite Automata Courses Regular Languages Courses Theoretical Computer Science Courses

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

System Validation: Automata and behavioural equivalences
EIT Digital via Coursera
Automata Theory
Stanford University via edX
理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX
离散数学概论 Discrete Mathematics Generality
Peking University via Coursera
Mecânica para a criação de autômatos de madeira
Domestika