If you want to make money online : Register now

[Solved]: Is there a complexity metric for finite state machines?

, ,
Problem Detail:

I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?

Yes, there is a canonical complexity metric for finite state machines: the number of states. It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric). We don't use a normalized metric based on the combination of such values. We just count the number of states.