Actually, there's one more trick I just remembered - you don't have to store an integer for `accept` at all, since you can arrange for the final state numbers t

Actually, there's one more trick I just remembered - you don't have to store an integer for `accept` at all, since you can arrange for the final state numbers to all be adjacent (usually, the first N positive integers; you probably want to save 0 as your fail state and use N+1 as your start state). If you have splitting you'll have to duplicate accept states, so you can't just count your regexes. For example: three_as = /aaa/ three_bs = /bba/ a_or_b = /[ab]/ accept_values = [error, a_or_b, a_or_b, three_as, three_bs] state 0: . -> 0; error state state 1: a -> 6, b -> 0; accept state after "a" state 2: a -> 0, b -> 7; accept state after "b" state 3: . -> 0; accept state after "aaa" state 4: . -> 0; accept state after "bba" state 5: a -> 1, b -> 2; start state state 6: a -> 3, b -> 0; intermediate state after "aa" state 7: a -> 0, b -> 4; intermediate state after "bb" Due to the splitting you probably can't construct your state machine with the correct numbers in the first place. But it's always trivial to renumber states after the fact using an array: Start with an array mapping each number to itself. [0, 1, 2, 3, 4, 5, 6, 7] For each state that needs a specific number, swap the numbers at those indices: For example, if we need 5 and 7 to be accept states, we would have: [0, 5, 7, 3, 4, 1, 6, 2] Optionally, sort your non-accept states so your table still looks pretty: [0, 5, 7, 1, 2, 3, 4, 6] Walk the states updating their contents according to the array. Finally, apply the permutation to the states themselves according to the array, mutating the array as you go. Clearly, by performing the same operation on both arrays we get the intended effect once the index array is sorted again. (That said, if you find this confusing, you can just do it while copying instead of in-place)