<p>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 <a href="http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory" rel="nofollow">http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory</a></p>

CC BY-SA 3.0
2012-01-15T22:46:00.353Z
2012-01-16T18:07:27.863Z
2012-01-16T18:07:27.863Z
anon
<p>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.</p>

<p>Clearly, if we join together pairwise any of the input/output channels of one or more FSM's, we obtain a new FSM. </p>

<p>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?</p>

<p>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)</p>

<p>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?</p>

CC BY-SA 3.0
2012-01-13T21:09:44.683Z
Also looking for Rreferences where similar questions have been asked
okok
CC BY-SA 3.0
2012-01-13T22:14:53.743Z
Crossposted and heavily edited under different name at [math.SE](http://math.stackexchange.com/questions/98642/visit-all-houses-in-m-times-n-town).
Raphael
CC BY-SA 3.0
2012-01-13T22:24:58.063Z
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
CC BY-SA 3.0
2012-01-13T23:25:58.930Z
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
CC BY-SA 3.0
2012-01-14T12:40:27.213Z
I am unfamiliar with the terminology in this area, please tell me if anything needs further clarification.
okok
CC BY-SA 3.0
2012-01-16T07:03:38.453Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
<computability><automata-theory>
Three questions about finite state machines
okok
# Three questions about finite state machines

(Asked by: username_0 on 2012-01-13)

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?

**Tags:** computability, automata-theory

> **Comments:**
> **username_0**: Also looking for Rreferences where similar questions have been asked  
> **username_1**: Crossposted and heavily edited under different name at [math.SE](http://math.stackexchange.com/questions/98642/visit-all-houses-in-m-times-n-town).  
> **username_1**: 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.  
> **username_2**: To anyone who is confused by the math.SE link provided by username_1: See the edit history (in particular the edit between revisions 6 and 7) of that math.SE question.  
> **username_0**: I am unfamiliar with the terminology in this area, please tell me if anything needs further clarification.  
> **username_3**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  

---

## 1 answers

### Answer by username_4 on 2012-01-15. Score: 3

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>


---

