Fun with finite state transducers

I recently1 solved an interesting problem inside zizmor with a type of state machine/automaton I hadn’t used before: a finite state transducer (FST). This is just a quick write-up of the problem and how I solved it. It doesn’t go particularly deep into the data structures themselves. For more information on FSTs themselves, I strongly recommend burntsushi’s article on transducers (which is what ac