Regular Expressions

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
E1-E2	difference
$ E	containment
E1 & E2	intersection
?	any symbol
A:B	pair
E1 x E2	cross-product
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 tool-box also provides regular expression operators for regular relations. For example, the expression

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}{a:b,b:c,c:a}*\end{verbatim}\end{minipage}$$ (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:

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}{b:[],? -b}*\end{verbatim}\end{minipage}$$ (2)

In this example¹, 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:

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}{a:b,b:c,c:a}* o {b:[],? -b}*\end{verbatim}\end{minipage}$$ (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:

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}% fsa -r '... ...b:c,c:a}* o {b:[],? -b}*' > ex1.fa \end{verbatim}\end{minipage}$$ (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 finite-automata tool-boxes such as AT&T's fsm program [18] and various visualization formats (including dot, vcg, daVinci, L^ATEX 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 on-line demo.