1. Introduction, Finite Automata, Regular Expressions
Channel:MIT OpenCourseWare · Length:1:00:34 · Published:2021-10-06 · Views:637368
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
- Disney's FastPass: A Complicated History · Defunctland · 1:42:59
- Half-Life 2: 20th Anniversary Documentary · Valve · 2:01:18
- The Continuity of Splines · Freya Holmér · 1:13:50
- How to Do 90% of What Plugins Do (With Just Vim) · thoughtbot · 1:14:02
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- How to Speak · MIT OpenCourseWare · 1:03:42
- 1. Introduction to Human Behavioral Biology · Stanford · 57:14
- LEADERSHIP LAB: The Craft of Writing Effectively · UChicago Social Sciences · 1:21:51
- MIT's Pathway to Fusion Energy (IAP 2017) - Zach Hartwig · MIT Plasma Science and Fusion Center · 1:11:39
- Stanford's Sapolsky On Depression in U.S. (Full Lecture) · Stanford · 52:28
- Justice: What's The Right Thing To Do? Episode 01 "THE MORAL SIDE OF MURDER" · Harvard University · 54:56
- Lec 1 | MIT 18.06 Linear Algebra, Spring 2005 · MIT OpenCourseWare · 39:49
- Randy Pausch's Last Lecture: Achieving Your Childhood Dreams · Carnegie Mellon University · 1:16:27
- Lecture 1A: Overview and Introduction to Lisp · MIT OpenCourseWare · 1:12:55
- Lecture 1A | MIT 6.001 Structure and Interpretation, 1986 · MIT OpenCourseWare · 1:12:55
- The Most IMPORTANT Video You'll Ever See (part 1 of 8) · wonderingmind42 · 9:17