Editing Finite-state transducer (section)

==Formal construction==

Formally, a finite transducer ''T'' is a 6-tuple ({{math|''Q'', Σ, Γ, ''I'', ''F'', δ}}) such that:

* {{mvar|Q}} is a [[finite set]], the set of ''states'';
* {{math|Σ}} is a finite set, called the ''input alphabet'';
* {{math|Γ}} is a finite set, called the ''output alphabet'';
* {{mvar|I}} is a [[subset]] of {{mvar|Q}}, the set of ''initial states'';
* {{mvar|F}} is a subset of {{mvar|Q}}, the set of ''final states''; and
* <math>\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q</math> (where ε is the [[empty string]]) is the ''transition relation''.

We can view (''Q'', ''δ'') as a labeled [[directed graph]], known as the ''transition graph'' of ''T'': the set of vertices is ''Q'', and  <math>(q,a,b,r)\in\delta</math> means that there is a labeled edge going from vertex ''q'' to vertex ''r''.  We also say that ''a'' is the ''input label'' and ''b'' the ''output label'' of that edge.

NOTE: This definition of finite transducer is also called ''letter transducer'' (Roche and Schabes 1997); alternative definitions are possible, but can all be converted into transducers following this one.

Define the ''extended transition relation'' <math>\delta^*</math> as the smallest set such that:

* <math>\delta\subseteq\delta^*</math>;
* <math>(q,\epsilon,\epsilon,q)\in\delta^*</math> for all <math>q\in Q</math>; and
* whenever <math>(q,x,y,r) \in \delta^*</math> and <math>(r,a,b,s) \in \delta</math> then <math>(q,xa,yb,s) \in \delta^*</math>.

The extended transition relation is essentially the reflexive [[transitive closure]] of the transition graph that has been augmented to take edge labels into account.  The elements of <math>\delta^*</math> are known as ''paths''.  The edge labels of a path are obtained by concatenating the edge labels of its constituent transitions in order.

The ''behavior'' of the transducer ''T'' is the rational relation [''T''] defined as follows: <math>x[T]y</math> [[if and only if]] there exists <math>i \in I</math> and <math>f \in F</math> such that <math>(i,x,y,f) \in \delta^*</math>.  This is to say that ''T'' transduces a string <math>x\in\Sigma^*</math> into a string <math>y\in\Gamma^*</math> if there exists a path from an initial state to a final state whose input label is ''x'' and whose output label is ''y''.

===Weighted automata===
{{see also|Rational series}}
Finite State Transducers can be weighted, where each transition is labelled with a weight in addition to the input and output labels. A Weighted Finite State Transducer (WFST) over a set ''K'' of weights can be defined similarly to an unweighted one as an 8-tuple {{math|1=''T''=(''Q'', Σ, Γ, ''I'', ''F'', ''E'', ''λ'', ''ρ'')}}, where:
* {{math|''Q'', Σ, Γ, ''I'', ''F''}} are defined as above;
* <math> E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K</math> (where ''ε'' is the [[empty string]]) is the finite set of transitions;
* <math>\lambda:  I \rightarrow K </math> maps initial states to weights;
* <math>\rho: F \rightarrow K </math> maps final states to weights.
In order to make certain operations on WFSTs well-defined, it is convenient to require the set of weights to form a [[semiring]].<ref name=BR16>{{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 | page=16 }}</ref> Two typical semirings used in practice are the [[log semiring]] and [[tropical semiring]]: [[Nondeterministic finite automaton|nondeterministic automata]] may be regarded as having weights in the [[Boolean semiring]].<ref name=Lot211>{{cite book | last=Lothaire | first=M. | author-link=M. Lothaire | title=Applied combinatorics on words | others=A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, [[Gesine Reinert]], [[Sophie Schbath]], Michael Waterman, Philippe Jacquet, [[Wojciech Szpankowski]], Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and [[Valérie Berthé]] | series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 | page=[https://archive.org/details/appliedcombinato0000loth/page/211 211] | url=https://archive.org/details/appliedcombinato0000loth/page/211 }}</ref>

Two weighted FST can be composed.<ref>{{Cite journal |last=Pereira |first=Fernando |last2=Riley |first2=Michael |last3=Sproat |first3=Richard |date=1994-03-08 |title=Weighted rational transductions and their application to human language processing |url=https://dl.acm.org/doi/10.3115/1075812.1075870 |journal=Proceedings of the workshop on Human Language Technology |series=HLT '94 |location=USA |publisher=Association for Computational Linguistics |pages=262–267 |doi=10.3115/1075812.1075870 |isbn=978-1-55860-357-8}}</ref>

===Stochastic FST===
Stochastic FSTs (also known as probabilistic FSTs or statistical FSTs) are presumably a form of weighted FST.{{citation needed|date=April 2017}}