0

自从我开始尝试找到解决此问题的方法以来已经 1 周了，我最终阅读了有关 CYK 算法的内容，但我不明白它对我有什么帮助。

所以我有一个特定的字符串作为开始，我们称之为startString。
我有一个特定的字符串，我想通过应用稍后解释的规则来获得它，称为stopString。

------------

现在让我们举个例子： 

startString = "A"  
stopString = "2403"

此示例的规则如下： 

A->BC  
B->D  
B->ED  
C->F  
C->FB  


E->0  
D->2  
D->3  
F->4  
E->1

该程序将采用上述输入并输出从 startString 到 stopString 的最小转换列表，可能如下： 

A->BC, B->D, C->FB, B->ED, D->2, F->4, E->0, D->3

------------

我的问题是：CYK 在这里如何帮助我？如何使用 CYK 从“A”获取“2403”？这个问题有没有更简单的解决方案？

4

1 回答 1

0

我将从用乔姆斯基范式写你的语法开始。目前有两条规则不满足此属性；即

B->D
C->F

解决此问题的一种天真的方法是将它们衰减为三个规则：

B->2 
B->3 
C->4

现在你的生产规则是

A->BC  
B->ED  
B->2 
B->3 
C->4
C->FB  
D->2  
D->3  
E->0  
E->1 
F->4

我正在使用的求解器（此处）不允许将数字作为终端。因此，我将创建一个双射映射

0 <-> a
1 <-> b
2 <-> c
3 <-> d
4 <-> e

新的目标字符串"cead"不是"2403". 将其插入我的求解器会产生生产规则。

Enter the start Variable A

Number of productions 11
A->BC
B->d
B->ED
C->e
C->FB
E->a
D->c
D->d
F->e
E->b
B->c

Enter string to be checked : cead
    A
          C
    A           B
   DB    CF     E    BD
String can be generated

不幸的是，由于天真的修复，规则有点模糊。但是，我认为这就足够了。

于 2016-11-22T12:04:58.963 回答