A method and apparatus are provided for optimizing finite state machines with labeled nodes. Under the method, labels from the nodes are shifted onto the labels of the links connected to the nodes. The finite state machine is then optimized. After optimization, the labels on the links are examined to verify that the prefixes of the labels on each outgoing link match the suffixes of the labels on each incoming link to a particular node. After this verification, a portion of a label on a link is removed from the link and inserted onto the node.