Large-scale finite state machines. An implementation is a method of splitting FSMs in which a dataflow graph is accessed that represents an expression. A cost analysis of computing sub-expressions of the expression corresponding to subsets of the dataflow graph is performed. Based on the cost analysis, the dataflow graph is split into separate dataflow graphs. A finite state machine is determined for each of the dataflow graphs. In another implementation, expressions are partitioned into groups that are implemented with respective FSMs without exploding the number of states in the FSMs. Another implementation is a computer-implemented method of relaxing a constraint when determining FSMs.