计算理论实验--CFG是P成员

计算理论第二个实验,比第一个复杂,本机测试通过,可是ACM上总是说我的结果是错误的。郁闷中..

 

算法是动态规划,按照书上的伪码描述写出代码,不过还不理解为什么算法可行。关于伪码描述,可以在这里查看:CFG是P成员

Problem description

上下文无关文法CFG G是否派生某个串W。采用动态规划(Dynamic Programming)设计一个一个多项式时间的验证算法。 实验方法: 编写一个算法/程序,对于给定的输入,可以在多项式时间内判定ACFG。 实验结果: 交一个程序验证。

Input

输入第一行为一个正整数n,接下来n行为一个满足乔姆斯基范式的文法描述。然后一个正整数m,接下来m行为m个小写字母组成的字符串(长度小于100) 表示m个待测试的串。

Output

对于没一个测试串返回"yes"或者"no",表示该串是否能被文法派生出来。

Sample Input

4
S->AB
A->AB|a
B->BC|b
C->CA|CC|c
3
ab
ac
bc

Sample Output

yes
no
no

 

本机测试结果

data.txt内容:

 

table.html内容:


3 行CFG文法规则如下:
S->RT
R->TR|a
T->TR|b

3 个待测字符串为:
baba 长度 = 4
ababb 长度 = 5
bbab 长度 = 4

串baba表格为:

T RT S SRT
R S S
T RT
R

串ababb表格为:

R S S
T RT S
R S
T
T

串bbab表格为:

T RT S
T RT S
R S
T

串 baba 接受状态: yes!


串 ababb 接受状态: no!


串 bbab 接受状态: yes!


31日更新

貌似是改了测试数据,有人ac了,不过我的代码却报超时。将内层循环移到外面之后,总算ac了。
下面是本机测试代码,稍加删除修改后即可提交。

One thought on “计算理论实验--CFG是P成员

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注