(5) |

The same mechanism is used to define *n*-ary operators, exploiting
Prolog variables. For instance, the containment operator `
containment(Expr)` is the set of all strings which have as a
sub-string any of the strings in ` Expr`. This could be defined as
follows:^{2}

(6) |

(7) |

We have found it useful to define boolean operators using this
mechanism. In fact, if we use the universal language to stand for *
true* and the empty language to stand for * false*, then the
standard operators for intersection and union correspond to
conjunction and disjunction:

(8) |

(9) |

The macros for true and false can also be used to define a conditional
expression in the calculus. The operator ` coerce_to_boolean`
maps the empty language to the empty language, and any non-empty
language to the universal language:

(10) |

Regular expression operator definitions can also be recursive. The
following example demonstrates furthermore that definitions can take
the operands of the operator into account. The operator `
set(List)` yields the union of the languages given by each of the
expressions in the list ` List`; ` union(A,B)` is a built-in
operator providing the union of the two languages ` A` and ` B`:

(11) |

We can also exploit the fact that these definitions are directly interpreted in Prolog by providing Prolog constraints on such rules. This possibility is used in [7] to define a longest-match concatenation operator which implements the leftmost-longest capture semantics required by the POSIX standard (cf. section 4.4).

A simple example is a generalization of the operator ` free`. Suppose
we want to define an operator ` free(N,Expr)` indicating the set of
strings which do not contain more than ` N` occurrences of `
Expr`. This can be done as follows:

(12) |

Another example is an implementation of the N-queens problem:
how to place N queens on an N by N chess-board in such a way that no
queen attacks any other queen. For any N we can create a regular
expression generating exactly all strings of solutions. A solution to
the N-queen problem is represented as a string of N integers between 1
and N. An integer *i* at position *j* in this string indicates that a
queen is placed on the *i*-th column of the *j*-th row.

(13) |

(14) |

The mechanism described sofar to define new regular expression
operators is already quite powerful. As another illustration, consider
the problem of compiling a given finite automaton into a regular
expression. This problem becomes trivial if we allow the introduction
of new operators. Here is the definition of an operator `fa/5' which
describes an automaton as a listing of its components:

(15) |

(16) |