If you read the proof in Hopcroft and Ullman, and you'll need to read it after this ...