1. 空性：对于R，若给定形式是自动机比如£-NFA，则等价于判定能否从初始状态到达接受状态，这需计算可达状态集合，若任一接受状态在里面，则为非空，否则为空。耗时不超过O(n^2)，n为自动机的状态数。若给定形式是正则表达式，则可先转为£-NFA，再计算可达状态集合，如此增多转化时间O(s)，s为正则表达式的长度。也可不转为自动机，直接根据基础归纳规则用递推法判定，耗时为O(s)。 对于CFL，等价于判定开始符号是否为产生的，若是则非空，否则为空。如直接用产生变元的基础归纳法计算，那耗时O(n^2)，n为文法G的规模，接近变元的个数。一个改进的算法实现，预先建立以变元为索引的数组、每个变元的链接（产生式内链接、产生式间链接），则耗时O(n)
2. 成员性：设串w的长度为n。对于R，等价于判定自动机能否接受w，若给定形式是DFA，则耗时O(n)。若给定形式是NFA，则耗时O(n*s^2)，s为状态数，如NFA有£转移，那需先计算它的闭包，耗时增多O(s^2)，可见总耗时还是O(n*s^2)。若给定形式是正则表达式，则先转为NFA，耗时增多O(r)，r为表达式的长度。 对于CFL，等价于判定从文法G的开始符号S能否推导出w，一般用CYK算法构造产生式三角表，再查看S是否属于表的顶点集合，若属于则能推导出w，否则不能，耗时为O(n^3)
posted on 2023-09-09 08:09
春秋十二月 阅读(39)
评论(0) 编辑 收藏 引用 所属分类:
Compute Theory