2022年10月11日(火) 13:12 Greg Wooledge <g...@wooledge.org>: > 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 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.
I also studied them more than ten years ago, but if I remember correctly, the negation of a regular language is also regular. First, the two representations of regular languages, concatenation+union+Kleene closure and DFA/NFA, are equivalent, meaning they can be converted either way. Then, the DFA of !(<pattern>) can be obtained by replacing the set of accept states in the DFA of <pattern> with its complement set. I guess it would generally become complicated if represented in a combination of concat+union+closure. Other complex patterns that contain !(<pattern>) as a subexpression can be constructed by just replacing "!(<pattern>)" with that complicated "concat+union+closure". -- Koichi
