Can we express the matching capabilities of Unix library function
glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, which is the minimal automata that we need?
For those that do not know what
glob() does, it is a pattern matcher generator using a few operators:
*matches an unlimited number of consecutive characters. As this can be in any position, not only in the end of the pattern, I eliminated the possibility of expressing glob expressions in terms of regular expressions.
?matches exactly one arbitrary character, which is similar to a skip state in a finite automaton.
[abc]matches an arbitrary-length string consisting of only symbols in the brackets, and
[!abc]matches an arbitrary-length string that includes anything but symbols in the brackets. Those character sets can also be listed in a shorthand notation like