But we will now see that even finding the minimum number of states is NP-complete, and inapproximable.
the general formulation of weighted automata (Berstel and Reutenauer, 1988) permits any weight set K, if appropriate operations ⊕ and ⊗ are provided for combining weights from the different arcs of the automaton.