Save this video free

CS 181 Lecture 11 -- Fall 2026, UCLA

Eli Jaffe · 1:25:40 · Watch on YouTube

Part of University of California, Los Angeles COM SCI 181. See all 5 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

Eli Jaffe completes the Myhill-Nerode argument that palindromes are not regular, then proves the state lower bound: K pairwise distinguishable strings require at least K DFA states. He introduces Turing machines as finite descriptions with a read-write tape, a movable head, and a finite control, and demonstrates bitwise complement and a tape-marking strategy for computing majority.

Key takeaways

Chapters

0:00 Distinguishing Palindrome Prefixes with Appended Strings
5:00 Infinitely Many Incompatible Zero Strings Rule Out a DFA
8:52 From Myhill-Nerode Lower Bounds to an Exact State Count
10:15 Counting Myhill-Nerode Classes for Ones Modulo Three
13:15 The Full Myhill-Nerode Theorem and Minimal DFA Size
16:06 Pigeonhole Proof of the DFA State Lower Bound
26:07 Why Finite Automata Give Way to Turing Machines
28:55 Relaxing DFA Input Access and Memory Restrictions
35:00 Turing Machine Tape, Input, and Finite Control
39:20 Turing Machine Transitions Read, Write, and Move
44:15 Running a Turing Machine and Defining Its Output
49:10 Turing Machine Output Conventions and Class Clarification
55:25 One-State Turing Machine Computes Bitwise Complement
59:05 Turing Machines Compute String-to-String Functions
1:03:33 Simulator Demonstrates Majority by Pairing Zeros and Ones
1:08:07 Majority Algorithm Scans, Marks, and Cleans the Tape
1:17:49 Local Transitions Produce Powerful Computation

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:02 All right, people at home, you missed 12 minutes. I apologize. Uh, all we really did was we revisited the proof that the majority function is not regular using toddler NFTt from last class. So, we rewent over this argument and now we are applying the same arguments to this pal function. I'm trying to show that the pound function is not regular using toddler >> 17. All right, let's come back together

0:57 and who has an idea? So, as a reminder, what we need, we need a set of n mutually incompatible string meaning they're not the same as each other under this ephobation like this is little mutually incompatible drink. So, what could be a jumping off point? >> Could be anything.

1:51 I mean, there's one really low hanging piece of fruit we've already seen recently. Okay. Who's who's who's got some good short-term memory? Yes. >> Sorry, I'm having a little trouble hearing you. I heard all ones and then all zeros and then something at the end. in the space they see. >> Okay. So, one string that's all zeros, one

2:39 string that's all ones. That's two strings. >> Precise. >> So, okay. I like there's some good ideas in here though. Uh, yes. >> Sorry. >> So, the question is we need to come up with a set of end strings. These end strengths should all be not equal to each other under this relationship. Meaning if I pick any two of them, there should be something I can append to the end of both of them. Same string to the end of both of them such that one is a palendrome and one isn't. That's our goal. >> Risa idea. Oh my god. See, somebody remembers what

3:29 we did five minutes ago. We could try

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Eli Jaffe.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.