| 一种构造正则表达式更小ε-NFA的方法 |
| |
| 引用本文： | 敬茂华,杨义先,于长永,辛阳.一种构造正则表达式更小ε-NFA的方法[J].东北大学学报(自然科学版),2013,34(9):1240-1243. |
| |
| 作者姓名： | 敬茂华 杨义先 于长永 辛阳 |
| |
| 作者单位： | 东北大学秦皇岛分校计算机与通信工程学院;东北大学信息科学与工程学院;北京邮电大学信息安全中心 |
| |
| 基金项目： | 国家自然科学基金资助项目(61100021,61121061,61202447);河北省自然科学基金资助项目(F2012501014);教育部高等学校博士学科点专项科研基金资助项目(20120042120009);河北省自然科学青年基金资助项目(F2013501048) |
| |
| 摘 要： | 基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用，提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理，然后构造每个分片的NFA，最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下，能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.
|
| 关 键 词： | 正则表达式 有限自动机 闭包 同态运算 构造算法 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《东北大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《东北大学学报(自然科学版)》下载免费的PDF全文 |
