[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 13:38:24 -0700

2022年10月11日(火) 13:12 Greg Wooledge <greg@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".


reply via email to

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