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.
Solution:
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).
Walk the DFA as follows: At each state, pick the largest character that leads to a state whose annotation is one smaller than the annotation of the current state. Stop when you reach a state that is annotated 0. The answer is the sequence of characters you've picked so far.