Previous Work

A possible implementation of the question mark operator is the introduction of a special symbol ? in finite state automata.² This special symbol is understood as `any alphabet symbol not mentioned in the automaton', in order to translate examples such as ?-a. This technique requires that each question mark operator is expanded into the set of symbols occurring in the regular expression as a whole. This solution (implemented in a previous version of the FSA Utilities [34] and in xfst, the Xerox regular expression compiler [18]) therefore leads to a proliferation of transitions. For example, the expression $(a..z \cdot ? - d)$ would result in an automaton with 52 transitions: 26 transitions from the initial state to an intermediate state for each of the letters of the alphabet and 26 transitions from this intermediate state to a final state for each of the letters except `d', as well as for ?.³

The idea to allow predicates on transitions instead of symbols is also mentioned in [37] and [38]. The details of this proposal, however, are not given. Apparently, in Watson's proposal predicates potentially inspect arbitrary parts of the input, and consume arbitrary prefixes of the input; the resulting formalism is therefore much more powerful, and hence various closure and efficiency properties are not applicable. In contrast, for the type of predicates proposed here, these attractive properties in fact are applicable, as is shown in the remainder of the article.