Q:

Three questions about finite state machines

Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it enters a loop and cant exit. 
Clearly, if we join together pairwise any of the input/output channels of one or more FSM's, we obtain a new FSM.  
Is there a finite set of FSM's, by which any other FSM can be built (using a finite number of each), by connecting channels pairwise? 
Can every FSM be built by the two state, 3 channel, FSMs specified by the map:
(A,1)->(B,2),(B,2)->(A,1),(B,1)->(B,1),(A,2)->(C,1),(C,1)->(A,2),(C,2)->(C,2)
Is there a general algorithm, given a set of FSMs, and a target FSM, to determine if the target can be built by any combination of any number of FSM's in the set? 

A:

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

