Re: bash core dumps doing glob pattern on long string

[Koichi Murase]

2022年10月11日(火) 16:22 Martin D Kealey <martin@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.