nlp - 如何执行 FST(有限状态转换器)组合

Question

考虑以下 FST:

T1 

0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a

T2

0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c

如何对这两个 FST(即 T1 o T2)执行组合操作
我看到了一些算法，但不太明白。如果有人能用简单的方式解释它，那将是一个很大的帮助。

请注意，这不是家庭作业。该示例取自提供解决方案的讲座幻灯片，但我不知道如何获得它。

Answer 1

由于您没有指定输入格式，我假设 0 是初始状态，任何出现在第二列但不是第一列的整数都是接受状态(T1 为 3，T2 为 2)，并且每一行是转换关系的一个元素，给出前一个状态、下一个状态、输入字母和输出字母。

对 FST 的任何操作都需要产生一个新的 FST，因此我们需要状态、输入字母表、输出字母表、初始状态、最终状态和转换关系(下面的 FST A、B 和 W 的规范按此顺序给出)。假设我们的 FST 是:

A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)

我们想找到

W = (R, Σ, Δ, R0, RF, ω) = A ∘ B

请注意，我们不需要确定 W 的字母；组合的定义就是这样做的。

想象一下串联运行 A 和 B，A 的输出磁带作为 B 的输入磁带。组合 FST 的状态只是 A 和 B 的组合状态。换句话说，组合的状态是各个 FST 状态的叉积。

R = Q × P

在您的示例中， W 的状态将是整数对:

R = {(0,0), (0,1), ... (3, 2)}

虽然我们可以重新编号这些并得到(例如):

R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}

类似地，组合 FST 的初始状态和接受状态是组件 FST 中的那些的叉积。特别是，R 接受一个字符串 iff A 和 B 都接受字符串。

R0 = Q0 × P0
RF = QF × PF

在示例中，R0 = {00} 和 RF = {32}。

剩下的就是确定过渡关系ω。为此，将 A 的每个转换规则与可能适用的 B 的每个转换规则结合起来。即组合A (qi, σ) → (qj, γ)的各个转移规则B 的每条规则都有一个“γ”作为输入字符。

ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}

在示例中，这意味着组合(例如)0 1 a : b T1 与 0 1 b : a和 1 2 b : a T2得到:

00 11 一个:一个
01 12 一个:一个

同样，您可以组合 0 2 b : b T1 与那些相同的 0 1 b : a和 1 2 b : a T2, 0 0 a : a T1 与 1 1 a : d和 1 2 a : c T2 & c.

请注意，您可能有无法访问的状态(那些永远不会作为“下一个”状态出现的状态)和永远不会发生的转换(那些来自无法访问的状态)。作为优化步骤，您可以删除这些状态和转换。但是，保留它们不会影响构造的正确性；这只是一个优化。