In standard regular expressions, the atomic symbols are normally treated `as is': these symbols represent themselves. In FSA6 the possibility exists to have these atomic symbols stand for arbitrary (user-defined) predicates instead. In order to use this possibility, a collection of declarations must be provided in a module. Such declarations define, for instance, what the conjunction is of two predicates. In a regular expression such as p1 & p2, where p1 and p2 are predicates, the resulting automaton is equivalent to p3 where p3 is the conjunction of p1 and p2.
The global variable pred_module defines the name of a module which is the module that is used (by default) to obtain the definitions of these declarations. Recognizers are associated with the name of such a module as well. Transducers have two such predicate module names: one for the domain and one for the range.
Two standard predicate modules are:
fsa_preds
fsa_frozen
In fsa_preds each predicate is a set of symbols or the complement of a set of symbols. Such sets of symbols are represented by a term
in(OrderedList)
not_in(OrderedList)
Moreover, in case OrderedList is a list with precisely a single element then the in/1 functor is dropped. The negated sets are useful to provide a treatment of the `any symbol' ?/0 operator. The predicate representing `any symbol' is represented by not_in([]). For example, the expression `? - a' will result in an automaton with a transition over not_in([a]).
The fsa_frozen module can be used for cases in which you want to treat symbols `as is'. If this module is used, you cannot use the ?/0 any symbol operator, or any of the operators which use this (such as the complement and term_complement operators). This predicate module is used internally for treating transducers temporarily as recognizers; e.g. if you want to determinize a transducer as if it were a recognizer by viewing each transition pair as an atomic unit. It is also used for the representation of weights in weighted automata.
If automata are combined using regular expression operators, then their corresponding modules must be identical. For instance, union of two recognizers implies that both recognizers have the same predicate module. Composition of two transducers imply that the predicate module of the output side of the first transducer is identical to the predicate module of the input side of the second transducer; the resulting transducer will take for its input side the input module of the first transducer, and as its output module it uses the output module of the second transducer.
This section lists the predicates that should be provided by a predicate module. An interesting example is provided by the fsa_preds module. A boring example is provided by the fsa_frozen module. In the Examples directory you will find a sub-directory PredModules which contains various other examples of predicate module declarations.
Pred is a predicate which is true for all symbols. This declaration is used to provide a translation for the `any symbol' operator ?/0. Predicate modules which do not define true/1 cannot employ this operator, and as a consequence cannot use operators which are defined in terms of ?/0. The predicate should succeed at most once.
This predicate translates the regular epxression notation into a predicate. This allows internal and external form of predicates; cf. display_predicate to translate from internal to an external form. Note: ?/0 is treated by the regular expression compiler itself, and uses true/1. The predicate should succeed exactly once.
This predicate should succeed if Pred is true of Symbol, and fail otherwise.
Predicate P is a predicate that is equivalent to the conjunction of P0 and P1. If the conjunction of P0 and P1 is inconsistent, then conjunction/3 should fail. The predicate should succeed at most once.
This predicate is used by the various visualization tools. It allows for the possibility to have an external format of a predicate. The predicate should succeed exactly once.
Cf. complement_of_set/3. This predicate is used in the complete/1 operator. It computes any information from the finite automaton Fa that is useful later in complement_of_set/3. This computation is then only performed once for each complete/1 operator. Term is an arbitrary term that is passed on to complement_of_set/3. The predicate should succeed exactly once.
Complements is a list of predicates such that the disjunction of that set is equivalent to the complement of the disjunction of SetOfPredicates. Set is some datastructure computed in preparation phase. This definition is used in the complete/1 operator. The predicate should succeed exactly once.
This code is required during the construction of deterministic automata, (the subset construction algorithm). Refer to the fsa_determinizer module for more details. In that module you can also find a definition of this predicate provided your predicate module has definitions for negation/2. In that case you can simply define:
determinize_preds(U0,U):-
fsa_determinizer:determinize_preds(U0,U,YourPredModule).
This declaration is used in determinize/1 The predicate should succeed exactly once.
This code is required during the construction of deterministic transducers, (the subset construction algorithm for transducers). Refer to the fsa_t_determinizer module for more details. In that module you can also find a definition of this predicate provided your predicate module has definitions for negation/2. In that case you can simply define:
t_determinize_preds(U0,U):-
fsa_t_determinizer:t_determinize_preds(U0,U,YourPredModule).
This declaration is used in t_determinize/1 The predicate should succeed exactly once.
If Pred0 is a predicate that is true of more than a single symbol, then Pred should be bound to '$@'(Pred0). If, on the other hand, Pred0 is true only of a single symbol, then Pred should be bound to Pred0. This is used in the computation of the regular operator identity/1. Predicate should succeed exactly once.
Used in cleanup/1 operator. List0 is a list of predicates (interpreted as disjunction). List is an equivalent (but shorter) list of predicates (interpreted as disjunction). This predicate is used to translate sets of transitions into smaller sets of transitions. The predicate should succeed exactly once.
Used in foreign language interface. If Pred is a predicate which `mentions' Sym then this should succeed. Otherwise it should fail.