# Introduction

## Weighted Finite State Transducers

Weighted finite state transducers (WFSTs) are graphs capable of translating an input sequence of symbols to an output sequence of symbols and associate a particular weight to this conversion.

Firstly we define the input and output symbols:

```
julia> isym = [s for s in "hello"];
julia> osym = [s for s in "world"];
```

We can construct a WFST by adding arcs, where each arc has an input label, an output label and a weight (which is typically defined in a particular semiring):

```
julia> using FiniteStateTransducers
julia> W = ProbabilityWeight{Float64} # weight type
julia> A = WFST(isym,osym; W=W); # empty wfst
julia> add_arc!(A,1=>2,'h'=>'w',1); # arc from state 1 to 2 with in label 'h' and out label 'w' and weight 1
julia> add_arc!(A,2=>3,'e'=>'o',1); # arc from state 2 to 3 with in label 'e' and out label 'w' and weight 0.5
julia> add_arc!(A,3=>4,'l'=>'r',1);
julia> add_arc!(A,4=>5,'l'=>'l',1);
julia> add_arc!(A,5=>6,'o'=>'d',1);
julia> initial!(A,1); final!(A,6) # set initial and final state
WFST #states: 6, #arcs: 5, #isym: 4, #osym: 5
|1/1.0|
h:w/1.0 → (2)
(2)
e:o/1.0 → (3)
(3)
l:r/1.0 → (4)
(4)
l:l/1.0 → (5)
(5)
o:d/1.0 → (6)
((6/1.0))
```

We can now plug the input sequence `['h','e','l','l','o']`

into the WFST:

```
julia> A(['h','e','l','l','o'])
(['w', 'o', 'r', 'l', 'd'], 1.0)
```

The input sequence is translated into `['w', 'o', 'r', 'l', 'd']`

with probability `1.0`

. A sequence that cannot be accepted will return a null probability instead:

```
julia> A(['h','e','l','l'])
(['w', 'o', 'r', 'l'], 0.0)
```

We could modify the WFST by adding an arc with an epsilon label, which is special symbol ϵ that can be skipped (see Sec. Epsilon label for more info):

```
julia> add_arc!(A,5=>6,'ϵ'=>'d',0.001);
julia> A(['h','e','l','l'])
(['w', 'o', 'r', 'l', 'd'], 0.001)
```

Here we used a small probability for this epsilon arc and this results in a low probability of the transduced output sequence. In fact the resulting probability of a sequence is the product of the weights of the arcs that were accessed (see Paths).

The method `(transduce::WFST)(ilabels::Vector)`

transduce the sequence of `ilabel`

using the WFST `fst`

requires the WFST to be input deterministic, see `is_deterministic`

.

See [1] for a good tutorial on WFST with the focus on speech recognition.