[Solved]: Language to Construct Finite State Transducer

Problem Detail: 

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?

Asked By : Gary D.

Answered By : Hendrik Jan

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".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28175

 Ask a Question

 Download Related Notes/Documents