On Tue, Oct 11, 2022, 3:12 PM Greg Wooledge <g...@wooledge.org> wrote:
> On Tue, Oct 11, 2022 at 12:38:44PM -0700, Koichi Murase wrote: > > 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. > > It's been too many decades since I studied this stuff in college, but > earlier while reading the thread I was pondering converting extglobs > into (ERE) regular expressions. > > Extglobs add 5 features: > > ?(pattern-list) > Matches zero or one occurrence of the given patterns > *(pattern-list) > Matches zero or more occurrences of the given patterns > +(pattern-list) > Matches one or more occurrences of the given patterns > @(pattern-list) > Matches one of the given patterns > !(pattern-list) > Matches anything except one of the given patterns > > The first 4 can be converted directly into ERE without any issues at all. > The last one cannot. At least not easily. > > The part I can't remember is whether !(foo) can be expressed in a regular > language. My gut says "no", but there might be some trick that I've > forgotten. A regular language has concatenation (abc), union (abc|def), > and close (a*bc*) but not negation. > Can't you just match and negate? >