Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Also looking for Rreferences where similar questions have been asked –  okok Jan 13 '12 at 21:09
2  
Crossposted and heavily edited under different name at math.SE. –  Raphael Jan 13 '12 at 22:14
2  
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
1  
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

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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