Safe Haskell	None
Language	Haskell98

FST.FSTStudio

Description

fstStudio takes a program consisting of regular relations that denotes the relation between two regular languages and constructs a transducer. If a regular expression, not a relation, is given, then it is interpreted as the identity relation. The syntax is very similar to Xerox's finite state transducer syntax with two fundamental differences: a distinction is made between functions (definitions) and strings, and fststudio allows functional definitions.

"a": A symbol. Example: ["b"] denotes the language {"b"}.
a: A variable. A symbol without quotes is a variable.
"a":"b": Describes a relation between the symbol a and b. This relation is ordered and a is said to be a part of the /upper language and b is said to be part of the lower language/. Example: ["a":"b"] denotes the relation {("a","b")}.
0: Epsilon symbol. The epsilon symbol denotes the string with no symbols. Example: [0] denotes the language {""}.
?: All symbol. The all symbol denotes the union of all symbols in the alphabet. Example: [?] and an alphabet {a,b,c} denotes the language {"a","b","c"}.
"": quotes cancel every special meaning of the symbols. Example: ["? 0"] denotes the language {"? 0"}.
@[A\: @] brackets are used to change the precedence of a regular relation.
(A): parenthesis expresses optionality, and has the same meaning as [A|0].
A B: Concatenation of the expressions or relations A and B. Example: [[a b] [c d]] denotes the language {"ac", "ad", "bc", "bd"}
A^n: Concatenation of A n times. A^0 is defined as the empty string. Example: [a]^3 describes the language {"aaa"}.
A|B: Union of the languages or relations A and B. Example: [a|b] describes the language {"a","b"}.
A & B: Intersection of the languages A and B. Example: [a b] & [a] describes the language {"a"}.
A - B: Minus of the languages A and B, and has the same meaning as [A & B]. Example: [a b] - [a] describes the language {"b"}.
~A: Describes the complement of an expression, and has the same meaning as [?* - A]. Note that complement is always defined over an alphabet. The expression [A] is only unambiguous with respect to an alphabet. Example: [a] denotes the language that doesn't contain the string "a". If the alphabet is {"a","b"} then [a] denotes the language {"","b","aa","ba",...}.
A+: Repetition (Kleenes plus). A concatenated with itself an arbitrary number of times, including zero times. Example: [a]+ denotes the infinite language {"a","aa","aaa",...}
A*: Kleene’s star: [A+ | 0]. Example: [a]* denotes the infinite language {"","a","aa",...}
$A: Containment. The set of strings where A appear at least once as a substring. Containment is the same thing as [?* A ?*].
A .x. B: Cross product of the languages A and B. Example: [[a b] .x. c] describes the relations {("a","c"), ("b","c")}.
A .o. B: Composition of the relations A and B. Example: [a:b c:d] .o. [d:e] describes the relation {("c","e")}.

The precedence of the operators is as follows, where 4 is the highest precedence:

.x. .o.
& -
Concatenation
~ ^ * + $

A file containing a program must end with .fst, and an input file mustend with .dat. A program is a collection of functions defining regular relations. A function with zero arguments is called a definition or a macro. A definition, or a macro, can for example look like this:

<digits> ::= "1" | "2" | "3" | "4" | "5" |
             "6" | "7" | "8" | "9" | "0" ;

and a function can look like this:

<swap,a,b> ::= b a ;

Note that strings are marked with quotes, and variables have no quotes. Every program must contain a <main> definition (a program without one will result in a parse error).

<main> ::= ... ;

The alphabet of a program is the symbols in the regular relation defined in the program.

Example program

<nickel>  ::= ["n" .x. "c"^5];
<dime>    ::= ["d" .x. "c"^10];
<quarter> ::= ["q" .x. "c"^25];
<cent>    ::= ["c" .x. "c"];
<money>   ::= [ <nickel> | <dime> | <quarter> | <cent>]*;
<drink>   ::= ["c"^65 .x. "PLONK"];
<main>    ::= [ <money> .o. <drink> ];

Batch mode

Usage: fst FILE [Options]. FILE must end with .fst, which defines an FstStudio program, or .net, which defines a saved transducer. If no options are given, then input is taken from standard input, the transducer is applied down, and the output, if any, is produced on standard output.

-u: Apply the transducer up
-d: Apply the transducer down
-i FILE: Take input from FILE
-o FILE: Write output to FILE

Interactive mode - list of commands

r REG: Read a regular relation from standard input. If a regular expression is typed, then it is interpreted as the identity relation.
b: Build an epsilon-free, deterministic, minimal transducer from a loaded/typed regular relation.
bn: Build an epsilon-free, possibly non-deterministic, non-minimal transducer from a load/typed regular relation.
m: Minimize a built transducer.
det: Determinize a built transducer.
s FILE: Save to FILE. If FILE ends with .net, then the built transducer is saved. Any other suffix saves the produced output in the system to FILE, if any.
l FILE: Load from FILE. FILE must end with .fst, .net or .dat. If FILE ends with .fst, then a FstStudio program is loaded into FstStudio. If FILE ends with .net, then a transducer is loaded into FstStudio. If FILE ends with .dat, then input is loaded into FstStudio.
l a | b: Load and union two transducers. a and b must either be a file ending with .net or the symbol *, which refers to the interior transducer. The produced transducer is possibly non-deterministic and non-minimal.
l a b: Load and concatenate two transducers. a and b must either be ale ending with .net or the symbol *, which refers to the interior transducer. The produced transducer is possibly non-deterministicand non-minimal.
l a*: Load and apply Kleene’s star on a transducer. a must either be a file ending with .net or the symbol *, which refers to the interior transducer. The produced transducer is possibly non-deterministicand non-minimal.
l a .o. b: Load and compose two transducers. a and b must either be a file ending with .net or the symbol *, which refers to the interior transducer. The produced transducer is possibly non-deterministic andnon-minimal.
vt: View loaded/built transducer.
vr: View loaded/typed regular relation.
vi: View loaded input.
vo: View produced output.
d: Apply transducer down with loaded input.
u: Apply transducer up with loaded input.
d SYMBOLS: Apply tranducer down with SYMBOLS.
u SYMBOLS: Apply transducer up with SYMBOLS.
c: Clear memory.
h: List commands.
q: End session.