&gt; Coincidentally FSTs and Radix trees share some similaritiesIndeed -- I think a useful way to comprehend FSTs is as a radix&#x2F;prefix trie that also allows suffix compaction. There&#x27;s probably a formal correlation proof between the two, but I don&#x27;t know it off the top of my head.

Radix Trees are (often?) used for this purpose, for example in Chi: <a href="https:&#x2F;&#x2F;github.com&#x2F;go-chi&#x2F;chi" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;go-chi&#x2F;chi</a>. Coincidentally FSTs and Radix trees share some similarities.

I&#x27;ve been thinking that FST could be well suited for building routers for web frameworks. I.e. matching request path `&#x2F;foo&#x2F;42` to a set of route patterns like `&#x2F;foo&#x2F;{id}` etc. As I understand FST should be near perfect for this use and could potentially allow very good performance. Especially if you can construct the FST at compile time. Somewhat surprisingly I haven&#x27;t seen anyone doing anything in that direction though, and FST literature is bit difficult if you don&#x27;t have formal NLP background

Actually pushdown transducers are even more fun (context free languages). 13 years ago I played around with visibly push down transducers for format conversion like grammar based binary compression on XML Schema. Can get you down a nice rabbit hole.

Author here.&gt; Probably some of the matching logic that could have been part of the FST is pushed into the normalizer instead.Yep, exactly -- there&#x27;s a great deal of prenormalization that in principle could be pushed into automata run over the FST instead. The reason I didn&#x27;t do that is laziness, but it&#x27;s the obvious next step :-)

Since it only needs to classify the result as one of &quot;fixed&quot;, &quot;structured&quot; or &quot;arbitrary&quot;, it doesn&#x27;t matter what the value of &quot;another_variable&quot; is, you&#x27;ll always be in the same state at the end. Finite state transducers can handle an infinite number of possibilities with a finite number of states just fine.It&#x27;s a bit strange though that the author constructs the FST to only recognize a finite list of strings. Probably some of the matching logic that could have been part of the FST is pushed into the normalizer instead.

I&#x27;m not quite sure I understand how they are applicable, since access patterns itself can be arbitrary complexFor example how is github.event.pull_request.labels[another_variable].name handled?

Fun with Finite State Transducers