# Unix glob() function and formal language equivalence

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 [a-z] or [!a-z].
• What are your thoughts? Are you familiar with regular expressions? Have you made any progress? Can you think of any relationship to anything you've learned in formal languages?
– D.W.
Mar 29 at 7:56
• I have learned formal languages in computer engineering school, and familiar enough with UNIX that I concluded glob() cannot be expressed in regular expressions. Mar 29 at 8:02
• I'm surprised to hear that. Can you give an example of something that cannot be expressed with a regular expression? I wonder if there is some aspect of glob I'm not familiar with. Perhaps you could edit the question to give some background on glob(), to specify the capabilities that you think are most challenging to model in that way? See also en.wikipedia.org/wiki/….
– D.W.
Mar 29 at 8:24