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?

  • $\begingroup$ Also looking for Rreferences where similar questions have been asked $\endgroup$ – okok Jan 13 '12 at 21:09
  • 2
    $\begingroup$ Crossposted and heavily edited under different name at math.SE. $\endgroup$ – Raphael Jan 13 '12 at 22:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 13 '12 at 22:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 13 '12 at 23:25
  • $\begingroup$ I am unfamiliar with the terminology in this area, please tell me if anything needs further clarification. $\endgroup$ – okok Jan 14 '12 at 12:40

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.