1
$\begingroup$

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].
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 29 at 7:56
  • $\begingroup$ I have learned formal languages in computer engineering school, and familiar enough with UNIX that I concluded glob() cannot be expressed in regular expressions. $\endgroup$ Mar 29 at 8:02
  • 1
    $\begingroup$ 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/…. $\endgroup$
    – D.W.
    Mar 29 at 8:24
1
$\begingroup$

Every glob expression can be recognized with a regular expression (the translation is straightforward). Every regular language is also context-free, and there is a straightforward translation: convert the regular expression to a DFA, then turn that into a pushdown automaton that never uses or looks at its stack. So, it follows that every glob expression can be recognized by some pushdown automaton, i.e., it recognizes a context-free language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.