1. Introduction, Finite Automata, Regular Expressions
Why Hacker News 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.
What it is
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.
Recommended by 4 HN commenters across 3 different months, 2021 to 2025.
What Hacker News said
Recommends sky2224 · 2024-06 · on “Recommended Books on Computational Complexity Theory”
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: [this video] .
Recommends trod123 · 2024-06 · on “Making AI better at math tutoring”
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 thinker alike despite being largely solved fields by experts in Computer Science, at least in terms of Computability Theory. Most of this work was completed in the 1950s. This is not a difficult a subject, but most people online simply are unwilling to do the work to rationally learn this and instead c
Recommends eterm · 2025-06 · on “The Princeton INTERCAL Compiler's source code”
> 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 [this 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
Recommends skydhash · 2025-08 · on “Traps to Developers”
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]: [this video]
Cites kjhughes · 2021-10 · on “MIT 18.404J – Theory of Computation [video]”
He addresses prerequisites specifically in the first lecture at this timestamp: [this video] (You're expected to be comfortable understanding mathematical theorems and producing proofs.)