Tas*_*eer 10 nlp finite-automata state-machine
考虑以下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)我看到了一些算法,但是不太了解.如果有人能够以一种简单的方式解释它,那将是一个重要的帮助.
请注意,这不是作业.这个例子来自给出解决方案的演讲幻灯片,但我无法弄清楚如何实现它.
out*_*tis 19
由于你没有指定输入格式,我假设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中的那些的交叉积.特别是,如果 A和B都接受字符串,则R接受字符串.
R0 = Q0 × P0 RF = QF × PF
在该示例中,R 0 = {00}并且R F = {32}.
剩下的就是确定过渡关系ω.为此,将A的每个转换规则与可能适用的B的每个转换规则组合.也就是说,将A的每个转换规则与具有"γ"作为输入字符的B的每个规则组合.(qi, ?) → (qj, ?)
? = { ((qi,ph), ?) → ((qj, pk), ?) : (qi, ?) → (qj, ?) ? ?,
(ph, ?) → (pk, ?) ? ?}
在该示例中,这意味着组合(例如)0 1 a : bT1 0 1 b : a和1 2 b : aT2以获得:
00 11 a : a 01 12 a : a
同样,你会结合0 2 b : bT1与那些同样0 1 b : a和1 2 b : aT2的,0 0 a : a与T1的1 1 a : d和1 2 a : cT2&C的.
请注意,您可能具有无法访问的状态(那些从未显示为"下一个"状态的状态)和永远不会发生的转换(来自无法访问状态的转换).作为优化步骤,您可以删除这些状态和转换.但是,留下它们不会影响施工的正确性; 这只是一个优化.
| 归档时间： |
|
| 查看次数： |
6041 次 |
| 最近记录： |