Lecture 5: CF Pumping Lemma, Turing Machines

Name: Lecture 5: CF Pumping Lemma, Turing Machines
Uploaded: 2021-10-06T12:47:06Z
Duration: 1 h 13 min 59 s
Description: Description: Quickly reviewed last lecture. Proved the CFL pumping lemma as a tool for showing that languages are not context free. Defined Turing machines (TMs). Defined TM deciders (halt on all inputs). Instructor: Prof. Michael Sipser

1:13:59

Up Next

Lecture 6: TM Variants, Church-Turing Thesis

Continue

Description: Quickly reviewed last lecture. Proved the CFL pumping lemma as a tool for showing that languages are not context free. Defined Turing machines (TMs). Defined TM deciders (halt on all inputs).

Instructor: Prof. Michael Sipser