Language to Construct Finite State Transducer

Question

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing.

You typically construct finite automata using regular expressions, for example (a | b).

What language does one typically use to construct Finite State Transducers?

You can't use Regular Expressions alone, because that defines only the input string, but I need some method to map corresponding output symbol. I have thought about having something like this ((a,x) | (b, y)), where the tuple (a,x) is composed of the component a input value, and the component x is the corresponding output value. Would that work in general for constructing FST?

Answer 1

Yes, such a specification would work. Basically a FST is a finite state automaton, with different labels on the edges. We can go from FST to regex by a standard algorithm. The same method works with transducers, only the labels are now pairs of strings. The concatenation of labels is done component-wise: $(a,x)(b,y) = (ab,xy)$.

There are several types of FST. To obtain a general one both input and output component are strings, not just letters. It is not difficult to see that alternatively one might require that both input and output are either a letter or the empty string.

All said, I personally prefer as a "language" the finite state graphs: they are easy to "program".

Answer 2

FSM Transducers are like DFAs with output states associated with input states. so transitions can be labeled as symbol pairs (x, y). see this page, Transducer section in the AT&T FSM library for one (simple) standard file format.

Answer 3

The direct product characterization described above is equivalent to the following which gives you the answer you're looking for: simply continue using regular expressions but subject them to commutativity xy = yx for all x in the input alphabet X and y in the output alphabet Y. The resulting algebra comprises the Kleene algebra of rational subsets of the monoid X^* x Y^* formed as the direct product of the two free monoids X^* and Y^*.

The transposition xy = yx may be viewed as the algebraic form of the "look ahead" operation.

Denoting the Kleene algebra comprising the rational subsets of a monoid M by RM; the factor algebras R X^* and R Y^* embed into R( X^* x Y^* ) as w in X^* |-> (w, 1) and v in Y^* |-> (1, v). So the general rank 1 term (w, v) may be written as either (w,1)(1,v) (which corresponds to taking the product in the order wv) or as (1,v)(w,1) (which corresponds to taking the product in the order vw). So you can simply do away with the construction-by-ordered pairs and write them as mentioned above: as regular expressions with the commutativity condition imposed on the underlying algebra.