Blog
Series:
3 posts
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
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
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