The fsa_interpreter contains various predicates to interpret finite automata. The following global variables influence the fsa_interpreter module:
interpreter
length_max
symbol_separator
symbol_separator_in
symbol_separator_out
nr_sol_max
This section lists the predicates defined by this module.
Succeeds if String is accepted by the regular expression in Atom. For example:
fsa_regex_accepts('[{a,b}*,b,a,b,{a,b}*]',"abbbbabababa").
String is a transduction of String0 according to the regular expression in Atom. Example:
fsa_regex_transduces('a:b',"a",L).
L = [98] ?
String is a transduction of String0 according to the regular expression in Atom. Example:
fsa_regex_transduces_w('[a:3,b:1*]',"abbb",L).
L = 6 ?
This predicate can be used both to recognize a given string or to produce a string according to Fa. This is why we use dif/2 below. We prefer functionality over efficiency here; note that the compiler-to-prolog implements the same functionality.
Making this code faster could be done for instance by indexing on source state and symbol. For deterministic automata, use the compiler-to-c for a fast and compact recognizer.
Since input can be non-deterministic we check for epsilon-cycles (the fifth argument of accepts/6 is a list of states visited after last consumption of input). Again, there are cases where it would make more sense to pre-compute efree automata first. But if that's the case you could do it, right?
StringOut is a transduction of StringIn according to transducer Fa.
This predicate employs a meta-notation in cases where loop-checking encounters a cycle. In that case the notation
|N+|
is written into the output string indicating that the previous N symbols could be repeated here as many times as desired. For example, consider the simple regular expression mapping an a to one or more b's:
a:(b+)
If a transduction is request for input string a, then the following outputs occur:
b
bb|1+|
In the second output string the meta-notation indicates that the second b could be repeated multiple times.
Many of the same remarks wrt fsa_accepts/2 apply here: works for non-instantiated input (lists with variable elements work OK, but variable length lists typically don't). Also takes care of identity constraints in the transducer, including delayed identity constraints and too early identity constraints, by using a non-proper implementation of queues which allow dequeue-ing before enqueue-ing! Examples to try, using the fsa_preds predicate module:
t_minimize([a:b,class(a..f)])
t_minimize({[a:b,?,?,?,?,?,b],[a:c,?,?,?,?,?,c]})
I think this is neat.
Weight is the weight assigned to String by Fa.
Similar to fsa_accepts/2 and fsa_transduces/3 above. However, we assume that there are no identity constraints. Loop-checking for [] input, but no meta-notation in output: we simply produce the minimum in such cases. That seems to be appropriate in most applications (?).
String is a Prolog string, and Regex is an atom that will be parsed as a regular expression. The system will match String approximately to that regular expression, returning each of the matches which require a minimal number of substitutions, insertions, deletions, and transpositions. A match is given by a recipe which is a list of Prolog terms as follows:
P:d deletion at position P
P:i(Pred) insertion of symbol for which Pred is true, at P
P:s(Pred) substitution of symbol for which Pred is true, at P
P:t transposition at position P
where P refers to the position in the sequence of symbols extracted from String where the corresponding edit operation takes place.
String is a Prolog string, and Fa is a finite automaton. The system will match String approximately to this Fa, returning each of the matches which require a minimal number of substitutions, insertions, deletions, and transpositions. A match is given by a recipe which is a list of Prolog terms as follows:
P:d deletion at position P
P:i(Pred) insertion of symbol for which Pred is true, at P
P:s(Pred) substitution of symbol for which Pred is true, at P
P:t transposition at position P
where P refers to the position in the sequence of symbols extracted from String where the corresponding edit operation takes place.
String0 and String is a Prolog string, Regex is an atom that will be parsed as a regular expression denoting a string to string transducer. The system will match String0 approximately to the domain of the regular expression, and return each of the transductions of these approximate matches.
String0 and String is a Prolog string, Fa a string to string transducer. The system will match String0 approximately to the domain of Fa, and return each of the transductions of these approximate matches.
String0 and String is a Prolog string, Regex is an atom that will be parsed as a regular expression denoting a string-to-weight transducer. The system will match String0 approximately to the domain of the regular expression, and return each of the transductions of these approximate matches.
String0 and String is a Prolog string, Fa a string to weight transducer. The system will match String0 approximately to the domain of Fa, and return each of the transductions of these approximate matches.