Supplemental Videos

Podcast: link

(Video) Overview

(Video) Vocabulary

(Video) Regular expressions introduction

(Video) Regular expressions

(Video) Regular expressions example

(Video) Regular expressions definition recap

(Video) Regular expressions more exmaples

(Video) Regular expressions and grep

(Video) DFA intro

(Video) DFA first examples

(Video) DFA first examples solution

(Video) JFLAP demo

(Video) DFA Formal Definition

(Video) DFA Analysis

(Video) DFA Design Example 1

(Video) DFA Design Example 2

(Video) DFA Design Example 3

(Video) Regular Languages

(Video) Finite Languages are Regular

(Video) Regular Languages and Complementation

(Video) Motivation for Closure Proofs

(Video) Regular Languages and Union

(Video) DFA Design Example: Intersection

(Video) Regular Languages and Intersection

(Video) Iterated Transition Function

(Video) NFA Motivation and Definition

(Video) NFA Overview and Example

(Video) NFA More Examples

(Video) NFA Formal Definitions

(Video) Regular Languages Union Again

(Video) Regular Languages Concatenation

(Video) Regular Languages Kleene Star

(Video) NFA to DFA

(Video) Extra Example

(Video) DFA to Regular Expression

(Video) Regular Expression to NFA

(Video) Nonregular Sets Introduction

(Video) Nonregular Sets Strategies

(Video) Pumping Lemma

(Video) Pumping Lemma and Finite Sets

(Video) Pumping Lemma Applications

(Video) Nonregular set example 1

(Video) Nonregular set example 1 proof

(Video) Nonregular set example 2 with pumping lemma

(Video) Nonregular sets summary

(Video) PDA introduction

(Video) PDA definition

(Video) PDA stack implementation

(Video) PDA formal definition

(Video) PDA example trace

(Video) PDA design example

(Video) PDA arrow labels

(Video) PDA Design and reverse engingeering

(Video) PDA Example Nondeterminism

(Video) PDA General Constructions

(Video) CFG introduction

(Video) CFG Design example

(Video) CFG Design for nonregular language

(Video) Context-free languages intro

(Video) CFL applications

(Video) CFL closure

(Video) Non-context-free languages

(Video) Turing machine introduction

(Video) Turing machine definition

(Video) TM state diagram

(Video) TM trace computation

(Video) TM complicated example

(Video) TM Intro Recap

(Video) TM Accept, Reject, Loop

(Video) TM Recognize vs Decide

(Video) TM Implementation-level and formal definition Example 1

(Video) TM Implementation-level and formal definition Example 2

(Video) TM Implementation-level and formal definition Example 3

(Video) Recognizable and Decidable languages

(Video) Regular languages are decidable

(Video) Equally expressive models

(Video) TM vs May Stay machines

(Video) Multitape TMs

(Video) Nondeterministic TMS

(Video) Church-Turing thesis

(Video) High-level descriptions of TMs

(Video) Closure of class of recognizable languages under union

(Video) Decidable computational problems

(Video) ADFA and EDFA and EQDFA

(Video) ADFA is decidable

(Video) AREX and ANFA are decidable

(Video) EDFA is decidable

(Video) EQDFA is decidable

(Video) Decidability proofs recap

(Video) Undecidability Counting Argument

(Video) ATM recognizable

(Video) ATM undecidable via diagonalization

(Video) ATM recap

(Video) Unrecognizable languages

(Video) Complement of ATM

(Video) Undecidability proof strategies

(Video) Reductions Intro

(Video) Mapping Reduction Definition

(Video) Computable Function Definition

(Video) Computable Function First Examples

(Video) Computable Function Complicated Example

(Video) Mapping Reduction Example 1

(Video) Mapping Reduction Example 2

(Video) Mapping Reduction Example 3

(Video) Halting Problem

(Video) Reducing A_TM to HALT_TM

(Video) Mapping Reducation Applications

(Video) Mapping Reduction Strategy

(Video) ETM is undecidable, part 1

(Video) Reduce ATM to ETM complement

(Video) Mapping reduction steps

(Video) EQTM

(Video) Complexity motivation

(Video) Complexity first definitions

(Video) Complexity classes examples

(Video) Complexity of ADFA

(Video) Nondeterministic time complexity

(Video) Feasible vs. verifiable

(Video) Polynomial time reductions

(Video) Using polynomial time reductions

(Video) NP completeness

(Video) SAT is NP complete