Finite Automate - solution part I

In my previous post "Finite Automata", I had posted two interesting exercises from well know texts. This post has their graphical solutions

Question 1 was

• Given a binary stream, can we develop a finite automata to calculate the binary number modulo 5?

Here is the graphical solution of the problem, one can simulate an input stream of 0's and 1's and verify the correctness

The start state is represented using a triangle and the accept state is represented by double boundary node. In this case both the start and accept state is "1".

Question 2 was

• Can we develop a finite automata that can validate the addition of two streams of binary numbers? Does such a finite automata exist?

There is one simplification we need to make to validate our results. For a given input of the form

0 1 1 <- Input1
0 0 1 <- Input2
1 0 0 <- Output

We need to present the string to the automata in the form [1 0 0][0 0 1][0 1 1]. We split the input and output into groups of threes, the last bit (MSB) represents the output. So for example, it says 1+1 is 0 and that is carried over and for the next input 1+0+ 1 (carry) is 0 and1 is carried over again. For the final input 0+0+1(carry) is 1. Hence this language is accepted by the finite automate.

Here is the graphical representation of the solution. In the next blog on FA, I'll discuss the techniques behind these solutions (which are probably very obvious to the reader of this blog anyway)


NOTE: states 7 and 8 are no good, but they are still shown here. Again, 3 is the start state and 3 and 4 are the accept states. The solution can be verified using two inputs and the output in the format specified above