If you want to make money online : Register now

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

, , No Comments
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?

Asked By : user2398029

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53878

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback