Function union 

pub fn union<W, F1, F2, M>(fst1: &F1, fst2: &F2) -> Result<M>
where
    W: Semiring,
    F1: Fst<W>,
    F2: Fst<W>,
    M: MutableFst<W> + Default,

Computes the union of two FSTs, creating an FST that accepts both languages.

Creates a new FST that accepts any string accepted by either input FST: $L(T_1 \cup T_2) = L(T_1) \cup L(T_2)$

Weights for strings in both languages combine via semiring addition: $(T_1 \cup T_2)(x) = T_1(x) \oplus T_2(x)$.

Arguments

• fst1 - The first input FST
• fst2 - The second input FST

Type Parameters

• W - Weight type implementing Semiring
• F1 - First FST type implementing Fst<W>
• F2 - Second FST type implementing Fst<W>
• M - Output FST type implementing MutableFst<W> and Default

Returns

A new FST accepting the union of the two input languages.

Errors

Returns Error::Algorithm if either input FST is invalid.

Examples

use arcweight::prelude::*;

// FST 1: accepts "a"
let mut fst1 = VectorFst::<TropicalWeight>::new();
let s0 = fst1.add_state();
let s1 = fst1.add_state();
fst1.set_start(s0);
fst1.set_final(s1, TropicalWeight::one());
fst1.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));

// FST 2: accepts "b"
let mut fst2 = VectorFst::<TropicalWeight>::new();
let s0 = fst2.add_state();
let s1 = fst2.add_state();
fst2.set_start(s0);
fst2.set_final(s1, TropicalWeight::one());
fst2.add_arc(s0, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s1));

// Union accepts both "a" and "b"
let result: VectorFst<TropicalWeight> = union(&fst1, &fst2)?;

// New start state + states from both FSTs
assert_eq!(result.num_states(), 1 + fst1.num_states() + fst2.num_states());

References

• John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.