Dr. Seuss and the Push-Down Automata
ROBERTNOACK.COM
Dr. Seuss, a well known children's author. But perhaps there is more to this guy that people originally thought? Sure he had a great brain and was very creative. He entertained and continues to entertain (by way of his published works) children around the country and the world. He helps young children become interested in reading.
People have constantly wondered where he got his ideas, and I think it is safe to say that since his death the world has been needing someone with creative influence such as him. Well I say, what better person than a computer scientist. After all everyone knows Dr. Seuss thought like a computer scientist. OH WAIT THEY DON'T?!?!
I will now present to you very brief evidence that Dr. Seuss
was indeed secretly a computer scientist.
First, I must remind you about some very basic things learned in theory of
computation. The Push-Down Automata, or PDA.
These machines are basically FAs (Finite Automata) only with a stack. Look at
this simple example with expresses the language 0^n1^n (a string of zeros
followed by a string of 1s containing an equal number of 0s and 1s):
This is a very simple PDA. Basically, your machine enters, writes a $ to the
stack, then reads all the zeros onto the stack, then reads ones and pops the
zeros off one by one. Then it reads the $ from the stack and accepts. Do you
remember PDAs now? Good.
Now that you are in a good state of mind let's look at this
picture which comes directly from a book, "The Sneeches" written by none other
than Seuss himself:
This is a machine in which a Sneech without stars upon thars can enter and then
they become a Sneech with a star.
How does someone think of this?!?! Well, after some consideration I realized,
this machine is simply a PDA!!
Check out this brief description:
A sneech enters the machine from the left. The sneech is read, nothing is
popped, and the star is pushed onto the sneech.
WHAT?!?