考虑以下 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)执行合成操作我看到了一些算法但不太了解。如果有人能以简单的方式解释它,那将是一个很大的帮助。
请注意,这不是家庭作业。该示例取自给出解决方案的演讲幻灯片,但我不知道如何解决。
考虑以下 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)执行合成操作我看到了一些算法但不太了解。如果有人能以简单的方式解释它,那将是一个很大的帮助。
请注意,这不是家庭作业。该示例取自给出解决方案的演讲幻灯片,但我不知道如何解决。
由于您没有指定输入格式,我假设 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 : b
T1 与0 1 b : a
T2的 和 组合1 2 b : a
以获得:
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
T2 1 2 a : c
&c 的和组合起来。
请注意,您可能有无法到达的状态(那些永远不会出现为“下一个”状态的状态)和永远不会发生的转换(那些来自无法到达的状态)。作为优化步骤,您可以删除这些状态和转换。但是,将它们留在里面不会影响构造的正确性;这只是一个优化。
如果您更愿意接受图形解释,下面的一组幻灯片提供了实践中组合算法的增量图形示例,还包括对分量传感器中 epsilon 转换的讨论。Epsilon 转换使合成过程复杂化,并且在这种情况下,outis answer 中描述的算法可能不会生成正确的结果,具体取决于所使用的半环。
有关一些图形示例,请参见幻灯片 10~35:
组合物T的状态是T1状态和T2状态的对。T 满足以下条件:
由于没有权重,我们可以忽略这一点。上面是从下面一张漂亮的纸上摘下来的。链接在这里