1. Introduction, Finite Automata, Regular Expressions

MIT OpenCourseWare · 628.1K views · 2021-10-06 · 1:00:34

Open on YouTube ↗

If playback is restricted in your region, try opening the original video. Use Mark watched to add it to your marked videos.

Overview

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.

On Hacker News

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.

Recommended by 4 HN people across 3 months · HN mentions 2021–2025

Topics

Computability & complexity theory University lectures & courses

What people said

skydhash · 2025-08 · Recommendation
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]
Read the original HN comment ↗

eterm · 2025-06 · Recommendation
> 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 reason well about it. Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota? So I've googled it now, and I've found the result is due to the "Pumping lemma": [LINK]
Read the original HN comment ↗

sky2224 · 2024-06 · Recommendation
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] .
Read the original HN comment ↗

Sources

Video by MIT OpenCourseWare, played through YouTube.

HN Library · Source license

Data and selection notes

HN summaries and labels may contain AI errors. HN dates refer to discussions, not video publication.

HN Library: HackerTube export (2026-10-31) and open-index/hacker-news. Upstream summaries and classifications may contain AI errors.

Views, duration and playback status refresh separately from the published catalog. When an update fails, existing data remains visible.

Selection checks

SaaS & AI candidates: Topic keywords do not match
Editor-approved picks: Editorial review is required

Rule matches identify candidates. They do not guarantee video quality or financial results.

About the library and its sources