Name: Anonymous 2009-01-09 2:25
So I started my foundations of computer science course today (finite state machines, Turing machines, computability, etc), and the professor handed out a bunch of stuff. Among this was a sample test from before, which had the following question:
Give an estimate of the maximum number of different four-state non-deterministic finite state accepters that can be on a three letter alphabet. Explain your answer.
Since I've already looked at some of the basics before, I was able to answer this, and then give a general solution for an alphabet of size n and an s-state machine. I then realized that given n and s, you could determine the number of bits necessary to represent the entire design of a non-deterministic finite state accepter. So then I had this idea: design a machine that takes in a string containing first 2 numbers (s and n) and then a series of 0's and 1's representing the nfsa to be simulated. The machine would be able to go back and forth and have some kind of auxiliary memory.
Discuss this /prog/, or have you only read SICP and nothing more?
Give an estimate of the maximum number of different four-state non-deterministic finite state accepters that can be on a three letter alphabet. Explain your answer.
Since I've already looked at some of the basics before, I was able to answer this, and then give a general solution for an alphabet of size n and an s-state machine. I then realized that given n and s, you could determine the number of bits necessary to represent the entire design of a non-deterministic finite state accepter. So then I had this idea: design a machine that takes in a string containing first 2 numbers (s and n) and then a series of 0's and 1's representing the nfsa to be simulated. The machine would be able to go back and forth and have some kind of auxiliary memory.
Discuss this /prog/, or have you only read SICP and nothing more?