How do find unique input and output for a finite state machine
How would I go about finding out whether each state has a unique input / output sequence? Is there a standardised technique or method? I can't seem to find anything online.
Thanks for any help!
For a Deterministic FSM (i.e., one without epsilon state transitions), there is a unique input sequence leading to the state if and only if the following conditions are met:
1) There must exist a path to the state. (An isolated unreachable state could not qualify).
2) There is no path that returns to the start state (otherwise, a direct march to the target state would reach it and a march that cycles back to the start state and then does a direct march would also work).
3) For each state S, either the target state is not reachable from S, or S is the target state, or there is a unique path from the start state to S and there is a unique path from S to the target state.
Assuming you are using a Directed Graph object representation, this will mean that there are no edges in the graph that terminate at the start state, and that for each state S in the graph, either, there is no path from S to the target, or there is a unique one.
If you are trying to find this out in code, you can probably use a modified Dijkstra's algorithm to address this.
Note that this only addresses having a unique input-sequence. Having a unique output sequence requires more care, because there may in fact be more than one input sequence that produces the same output sequence. However, the ideas are the same, but you must modify the third criteria:
3) For each state S, either the target state is not reachable from S, or S is the target state, or if S and T both have a path to the target state, they must generate the same output sequence, and the output sequence generated from the start state to S and the output sequence generated from the start state to T must be the same.
Again, a modified Dijkstra's is probably the best bet.