27 episodes

This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser. The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines.

There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's theorem that NP-complete problems exist. In addition to these major results, and other results, a central goal of the course is to increase student's skill level in understanding and writing rigorous mathematical proofs.

Theory of Computation - Fall 2011 UC Davis

    • Technology
    • 5.0 • 4 Ratings

This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser. The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines.

There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's theorem that NP-complete problems exist. In addition to these major results, and other results, a central goal of the course is to increase student's skill level in understanding and writing rigorous mathematical proofs.

    • video
    L1: Introduction to Finite-state Machines, Regular Languages

    L1: Introduction to Finite-state Machines, Regular Languages

    This introduction covers deterministic finite-state machines and regular languages.

    • 1 hr 6 min
    • video
    L2: Regular Languages and non-deterministic FSMs

    L2: Regular Languages and non-deterministic FSMs

    Operations on regular languages, union and concatenation. Introduction
    to non-deterministic finite state machines.

    • 1 hr 20 min
    • video
    L4: Regular Expressions

    L4: Regular Expressions

    Introduction to Regular Expressions: Formal recursive definition of a regular expression; composition rules for regular expressions; operators on regular expressions; start of proof of the equivalence of regular expressions and regular languages.

    • 1 hr 18 min
    • video
    L5: Regular expressions, regular languages, and non-regular languages

    L5: Regular expressions, regular languages, and non-regular languages

    Completion of equivalence of regular languages and regular expressions. Introduction to the proof that there are languages that are not regular; first an ad hoc proof using the essence of the pumping lemma, but without formally stating it.

    • 1 hr 17 min
    • video
    L6: The Pumping Lemma, and introduction to CFLs

    L6: The Pumping Lemma, and introduction to CFLs

    A formal treatment of the pumping lemma for regular languages, and its use in proving that certain languages are not regular. Introduction to context free languages and grammars.

    • 1 hr 16 min
    • video
    L7: Contex-Free Grammars and Push-Down Automata

    L7: Contex-Free Grammars and Push-Down Automata

    Review of CFLs and grammars; overview of basic results of CFLs without proofs. Introduction to push-down automata (PDA). Statement of the equivalence of CFLs and DPAs.

    • 1 hr 18 min

Customer Reviews

5.0 out of 5
4 Ratings

4 Ratings

Top Podcasts In Technology

Lex Fridman
Jason Calacanis
Jack Rhysider
NPR
Gimlet
Jason Calacanis

More by UC Davis

Margaret Swisher and Barbara Myslik
Ann Stevens
Hilary Hoynes
Maynard Amerine
Victoria Cross