Oh! Gosh I can see it already, this is going to be a long post. Here is a brief background, I recently found my copy of Michael Sipser's
Introduction to the Theory of Computation lying around. I found that is was rather nice to read (compared to some of the earlier texts I had been reading) and on finishing the first chapter stumbled upon some interesting problems posed in different forms in Sipser's, Ullman's and Papadimitriou's book.
I am going to cover some interesting aspects of Automata in this blog entry
- The exercises in this blog entry to provoke some thought
- Their solutions and representation in the next blog entry
- A software to help solve/validate some of the solutions to the exercises
The exercises I am going to cover are
- Given a binary stream, can we develop a finite automata to calculate the binary number modulo 5?
- Can we develop a finite automata that can validate the addition of two streams of binary numbers? Does such a finite automata exist?
Now that you have some food for thought, come back here and check to see what I did with these problems/exercises at little later in the next blog post
