1. Introduction, Finite Automata, Regular Expressions

Channel:MIT OpenCourseWare · Length:1:00:34 · Published:2021-10-06 · Views:637368

Watch on YouTube

Summary

The first lecture of Michael Sipser's MIT 18.404J Theory of Computation course, covering course mechanics, finite automata, regular languages and regular expressions. It proves closure of regular languages under union and begins concatenation.

Why HN recommends it

HN recommends Sipser's free lectures as the companion to the standard theory of computation textbook and a path to understanding how computers fundamentally work.

Sipser also has corresponding lectures that are available for free on YouTube here — HN, 2024

Computability & complexity theory · University lectures & courses

Subtitles (excerpt)

[SQUEAKING] [RUSTLING] [CLICKING] MICHAEL SIPSER: So, welcome, everybody, to the Fall 2020 online Introduction to the Theory of Computing 18.404/6.840. My name is Mike Sipser. I'm going to be your instructor for the semester in this class. So let me just tell you what the course is about. Basically, it's going to be in two halves. We're going to be talking about what are the capabilities and limitations of computers-- of computer algorithms, really, computation. And the two parts of the course are more or less divided in half. The first half of the course is going to talk about a subject called computability theory, which it really asks what you can compute with an algorithm in principle. That's-- was an active area of research in the earlier part of the 20th century. It's pretty much closed off as a research subject these days, mainly because they answered all of their big questions. And so a mathematical field really only stays vital when it has problems to solve, and they really solved all of their interesting problems-- for the most part, not 100%. But for the most part, it sort of finished off in the 1950s-- just to say a little bit more about what we're going to talk about there.

On Hacker News

It's half a chapter in most books I know. Or a subset of this 1h MIT videos [0], but the instructor also explains Finite Automata which is the basic mechanism that does all the stuff. [0]: [VIDEO] — skydhash, 2025-08
> if you require your parens to be balanced, that's no longer a regular language. TIL: [LINK] As someone who has only recently learned the formal definition of regular language ( Thanks to [VIDEO] as mentioned on this board recently ), I'm interested in the formal proof for this? It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet re… — eterm, 2025-06
As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: [VIDEO] . — sky2224, 2024-06
AI won't ever be able to teach math because AI cannot reason. It handles information very differently than humans do. It is at best a flawed oracle that may lie through omission without you being able to tell. This is supported by the fact that there are hard limits to computation, in terms of both Computability Theory, and Complexity Theory that are often disregarded by the novice and magical th… — trod123, 2024-06
He addresses prerequisites specifically in the first lecture at this timestamp: [VIDEO] (You're expected to be comfortable understanding mathematical theorems and producing proofs.) — kjhughes, 2021-10

Related videos