Finding the shortlex predecessor
Problem: You have a DFA M and a string s that matches it. You want to find the shortlex-predecessor to s in the language matched by the DFA.
Create the P which matches all strings that are strictly shortlex smaller than s. Build the product DFA M' which intersects M with P, matching all strings matched by M that are shortlex predecessors of s.
Now annotate each state in M' with the length of the longest matching string starting from there (this is possible because there is an upper bound on the length of strings matched by M' and is easy to calculate recursively with dynamic programming because this means there are no loops in the DFA).