Three questions about finite state machines
No there are some FSA which are irreducible, I believe the 2 state 3 input FSA you give is the flip-flop, every reducible FSA can be made by this one. Start by looking here and the references given http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory