Theory of Computation

Every post in the "Theory of Computation" series, in reading order. · 3 posts

1. Part 1

   What Can Computers Actually Solve, and How Do We Know?

   An intro to the theory of computation — decision problems, formal languages, and regular expressions explained through the lens of what machines can and cannot do

2. Part 2

   Patterns Look Different When a Machine Has to Actually Check Them

   How regular expressions formally describe patterns, and how DFAs — the simplest possible machines — actually verify them, one character at a time

3. Part 3

   Regular Languages Stay Regular No Matter What You Do to Them

   How to build DFAs for specific patterns, why flipping accept states gives you the complement, and how running two machines in parallel proves closure under union