2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Also looking for Rreferences where similar questions have been asked $\endgroup$
    – okok
    Jan 13, 2012 at 21:09
  • 2
    $\begingroup$ Crossposted and heavily edited under different name at math.SE. $\endgroup$
    – Raphael
    Jan 13, 2012 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, 2012 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, 2012 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, 2012 at 12:40

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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