Regular expressions

The following options can be used to construct automata for regular languages on the basis of the language(s) defined by one or more input automata:

-concat File1 File2

-kleene File1

-union File1 File2

-reverse File1

-intersect File1 File2

-complement File1

-difference File1 File2

These options can be used to combine automata by concatenation, Kleene closure, union, reversal, intersection, complementation or difference respectively. Examples:

% fsa -complement <aabb.d start(q4). final(q5). final(q6). final(q7). trans(q5,a,q5). trans(q5,b,q5). trans(q4,a,q7). trans(q4,b,q6). trans(q8,a,q5). trans(q8,b,q6). trans(q6,a,q5). trans(q6,b,q8). trans(q7,a,q4). trans(q7,b,q5).

(20)

Because the system assumes that the alphabet consists only of the symbols occurring in the input automaton, it may be safer to use the -difference option. In this case an automaton is written to standard output, defining all strings that are defined by the automaton in File1 except for the strings defined in File2. For example, if the file abc.nd consists of the automaton defining all strings over the alphabet {a,b,c}, then we get:

% fsa -difference abc.nd aabb.nd start(q9). final(q10). final(q11). final(q12). trans(q9,a,q12). trans(q9,b,q11). trans(q9,c,q10). trans(q10,a,q10). trans(q10,b,q10). trans(q10,c,q10). trans(q11,a,q10). trans(q11,b,q13). trans(q11,c,q10). trans(q12,a,q9). trans(q12,b,q10). trans(q12,c,q10). trans(q13,a,q10). trans(q13,b,q11). trans(q13,c,q10).

(21)

The system also supports the construction of an automaton on the basis of a regular expression: the option -r Expression can be used. The operators that are allowed are Kleene closure (*), concatenation (.) and union (;). Moreover, it is possible to have transduction pairs (:). Finally, the system understands intervals. The expression a-z is a shorthand for the expression a;b;c;..;z. For example:

% fsa -r '(a*;b*).(d-g)*' | fsa -ps

(22)

produces the following postscript picture: