公开(公告)号：CN103632048A

公开(公告)日：2014-03-12

申请号：CN201310589762.5

申请日：2013-11-20

Applicant: 中国科学院信息工程研究所

Inventor： 孙永 ,  柳厅文 ,  刘洋 ,  杨威 ,  刘庆云 ,  郑超 ,  杨嵘 ,  周舟

IPC: G06F19/00

Abstract: 本发明涉及一种度量正则表达式状态复杂度的方法及装置。度量正则表达式状态复杂度的方法包括：步骤一，判断给定非确定型有限自动机M中任意两状态p、q间的卷曲关系，该卷曲关系为如下五种关系之一：互斥关系、等价关系、包含于关系、包含关系、独立关系，M=(Q,Σ,δ,q0,F)，其中，Q是一个有穷集，Q的每个元素称为一个状态,Σ是一个有穷字母表，Σ的每一个元素称为一个输入字符,δ是状态转移函数,q0∈Q,q0是唯一的一个开始状态,F是终止状态集；步骤二，根据步骤一的判断结果估计正则表达式的状态复杂度，该状态复杂度即对M确定化得到的确定型有限自动机M′的状态数目|Q′|，M′=(Q′,Σ,δ′,q0′,F′)。本发明的度量正则表达式状态复杂度的方法及装置，能够快速地得到一个合理的估计值，提高度量效率。