10

考虑以下 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)执行合成操作我看到了一些算法但不太了解。如果有人能以简单的方式解释它,那将是一个很大的帮助。

请注意,这不是家庭作业。该示例取自给出解决方案的演讲幻灯片,但我不知道如何解决。

4

3 回答 3

20

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

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

A = (Q, Σ, Γ, Q 0 , Q F , α)
B = (P, Γ, Δ, P 0 , P F , β)

我们想找到

W = (R, Σ, Δ, R 0 , R F , ω) = 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 中的叉积。特别是,当 A 和 B 都接受字符串时,R 接受字符串

R 0 = Q 0 × P 0 
R F = Q F × P F

在示例中,R 0 = {00} 和 R F = {32}。

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

ω = { ((q i ,p h ), σ) → ((q j , p k ), δ) : (q i , σ) → (q j , γ) ∈ α,
                                     (p h , γ) → (p k , δ) ∈ β}

在该示例中,这意味着将(例如)0 1 a : bT1 与0 1 b : aT2的 和 组合1 2 b : a以获得:

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

同样,您可以将0 2 b : bT1 与相同的0 1 b : a1 2 b : aT2 组合,0 0 a : a将 T1 与1 1 a : dT2 1 2 a : c&c 的和组合起来。

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

于 2010-04-15T23:46:14.577 回答
4

如果您更愿意接受图形解释,下面的一组幻灯片提供了实践中组合算法的增量图形示例,还包括对分量传感器中 epsilon 转换的讨论。Epsilon 转换使合成过程复杂化,并且在这种情况下,outis answer 中描述的算法可能不会生成正确的结果,具体取决于所使用的半环。

有关一些图形示例,请参见幻灯片 10~35:

http://www.gavo.tu-tokyo.ac.jp/~novakj/wfst-algorithms.pdf

于 2012-01-30T07:50:23.077 回答
1

T1 和 T2T1 和 T2

T1 和 T2 的组成T1.T2(组成

组合物T的状态是T1状态和T2状态的对。T 满足以下条件:

  1. 它的初始状态是T1的初始状态和T2的初始状态的对
  2. 它的最终状态是 T1 的最终状态和 T2 的最终状态的对
  3. 对于从 q1 到 r1 和 T2 从 q2 到 r2 的每一对转换 T1,存在从 (q1, q2) 到 (r1, r2) 的转换 t,使得 T1 的输出标签与 T2 的输入标签匹配。转换 T 从 T1 获取其输入标签,从 T2 获取其输出标签,其权重是 T1 和 T2 的权重的组合,该操作通过沿路径组合权重的相同操作完成。

由于没有权重,我们可以忽略这一点。上面是从下面一张漂亮的纸上摘下来的。链接在这里

于 2020-02-17T13:12:10.433 回答