专利详情

专利名称	度量正则表达式状态复杂度的方法及装置
申请号	CN201310589762.5	专利类型	发明专利
公开（公告）号	CN103632048A	公开（授权）日	2014.03.12
申请（专利权）人	中国科学院信息工程研究所	发明（设计）人	孙永;柳厅文;刘洋;杨威;刘庆云;郑超;杨嵘;周舟
主分类号	G06F19/00(2011.01)I	IPC主分类号	G06F19/00(2011.01)I
专利有效期	度量正则表达式状态复杂度的方法及装置至度量正则表达式状态复杂度的方法及装置	法律状态	实质审查的生效
说明书摘要	本发明涉及一种度量正则表达式状态复杂度的方法及装置。度量正则表达式状态复杂度的方法包括：步骤一，判断给定非确定型有限自动机M中任意两状态p、q间的卷曲关系，该卷曲关系为如下五种关系之一：互斥关系、等价关系、包含于关系、包含关系、独立关系，M=(Q,Σ,δ,q0,F)，其中，Q是一个有穷集，Q的每个元素称为一个状态,Σ是一个有穷字母表，Σ的每一个元素称为一个输入字符,δ是状态转移函数,q0∈Q,q0是唯一的一个开始状态,F是终止状态集；步骤二，根据步骤一的判断结果估计正则表达式的状态复杂度，该状态复杂度即对M确定化得到的确定型有限自动机M′的状态数目\|Q′\|，M′=(Q′,Σ,δ′,q0′,F′)。本发明的度量正则表达式状态复杂度的方法及装置，能够快速地得到一个合理的估计值，提高度量效率。