context-free-grammar - 随机上下文无关文法到乔姆斯基范式

Question

我实际上不明白如何将 scfg 转换为 cnf。我知道如何转换cfg。我应该如何处理概率？

例子：

S->c W1 g:0.9|c W:0.1
W1->g W2 u:0.8|W2 u:0.2
W2->g W3 c:0.6|a W3 u:0.4
W3->g W4 c:0.5|W4 c:0.5
W4->a W5:0.7|c W5:0.3
W5->u W6:0.9|g W6:0.1
W6->a:0.6|u:0.4

我也在寻找有关预测二级 RNA 结构的任何信息（完美的一些代码示例）。我会很高兴得到帮助！

Answer 1

好的，我用 CNF 解决了我的问题。如果有人对 CNF 中的 SCFG 感兴趣：

S->C K:0.9|C W1:0.1
C->c:1.0
K->W1 L:1.0
L->g:1.0
W1->L J:0.8|J:0.2
J->W2 H:1.0
H->u:1.0
W2->L U:0.6|Y T:0.4
Y->a:1.0
T->W3 H:1.0
U->W3 O:1.0
O->c:1.0
W3->L R:0.5|W4 O:0.5
R->W4 O:1.0
W4->Y W5:0.7|O W5:0.3
W5->H W6:0.9|L W6:0.1
W6->a:0.6|u:0.4