[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: bash core dumps doing glob pattern on long string

From: Koichi Murase
Subject: Re: bash core dumps doing glob pattern on long string
Date: Tue, 11 Oct 2022 12:38:44 -0700

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]