2022年10月11日(火) 16:22 Martin D Kealey <mar...@kurahaupo.gen.nz>: > However I note that it's not always possible to make a Deterministic FSA > when you have repeatable groups which themselves don't have fixed lengths > (like a+(a|abbba|aabb*aba)b);
This is not true. Any non-deterministic finite automaton (NFA) can be translated into a deterministic finite automaton (DFA). The "regular expressions" that must be processed by stacking/recursion for backtracking are typically the ones that involve backreferences, \1, \2, etc., to capturing groups in the same pattern. However, such "regular expressions" no longer define regular languages and cannot be represented by NFAs (strictly speaking, unless all the referenced capturing groups accept finite languages) because we need infinite states to record the captured strings. As far as I know, glob/extglob does not have constructs that cannot be represented by formal regular languages so should always be able to be represented by NFAs and thus DFAs.