Next: Extendible Regular Expression Operators
Up: An Extendible Regular Expression
Previous: Introduction
Table 1:
Basic regular expression operators in FSA5.
[] 
empty string 
[E1,E2,...En] 
concatenation of E1, E2 ...En 
{} 
empty language 
{ E1,E2,...En} 
union of E1, E2 ...En 
E* 
Kleene closure 
E^ 
optionality 
~E 
complement 
E1E2 
difference 
$ E 
containment 
E1 & E2 
intersection 
? 
any symbol 
A:B 
pair 
E1 x E2 
crossproduct 
A o B 
composition 
domain(E) 
domain of a transduction 
range(E) 
range of a transduction 
identity(E) 
identity transduction 
inverse(E) 
inverse transduction 

Table 1 gives an overview of the basic regular expression
operators provided by FSA5. Apart from the
standard regular expression operators and extended regular expression
operators for regular languages, the toolbox also provides regular
expression operators for regular relations. For example, the
expression

(1) 
is the transducer which rewrites each a into a b, each
b into a c, and each c into an a. Consider
furthermore a transducer which removes each b, but which leaves
each non b in place:

(2) 
In this example^{1}, the expression ? b
is any symbol except
b. An expression Expr denoting a regular language is
automatically coerced in the context in which a transducer is expected
into identity(Expr). Here, ? b
is automatically coerced
into identity(? b)
, because it is unioned with a transducer.
Composing the examples 1 and 2:

(3) 
yields a transducer which removes each a, and transduces each
b to a c, and each c to an a. For instance,
the input abcabcabc yields cacaca.
In FSA5, such a regular expression could be turned into a transducer
using the command:

(4) 
In this case, the resulting automaton is written to the file
ex1.fa in FSA5 format. There are options to produce automata in
many different formats, including formats for other finiteautomata
toolboxes such as AT&T's fsm program [18] and various
visualization formats (including dot, vcg, daVinci,
L^{A}TEX and postscript). Other interesting formats are as a
Prolog or C program implementing the transduction.
FSA5 can also be used interactively. In that case a graphical user
interface is provided from which regular expressions can be input. The
resulting automata are then displayed on the screen, and the resulting
automata can be tested with sample inputs. The availability of such a
graphical user interface in combination with various visualization
tools has enabled the use of FSA5 in teaching [3].
For more information on
these and other possibilities refer to the FSA Home Page:
http://www.let.rug.nl/vannoord/Fsa/. The FSA Home Page includes
an online demo.
Next: Extendible Regular Expression Operators
Up: An Extendible Regular Expression
Previous: Introduction
20000703