Friday, October 23, 2009

Finite Automata (post one of many to come)

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

  1. Given a binary stream, can we develop a finite automata to calculate the binary number modulo 5?
  2. 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
Post a Comment