# 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?

-
Also looking for Rreferences where similar questions have been asked – okok Jan 13 '12 at 21:09
Crossposted and heavily edited under different name at math.SE. – Raphael Jan 13 '12 at 22:14
You are on a site dedicated to theoretical computer science. Please stop beating around the bushes and state your question in a clear way already. The last sentence suggests you want to talk about automata. Please drop the metaphor; we know what automata are. – Raphael Jan 13 '12 at 22:24
To anyone who is confused by the math.SE link provided by Raphael: See the edit history (in particular the edit between revisions 6 and 7) of that math.SE question. – Tsuyoshi Ito Jan 13 '12 at 23:25
I am unfamiliar with the terminology in this area, please tell me if anything needs further clarification. – okok Jan 14 '12 at 12:40
show 1 more comment