10.3969/j.issn.1005-3026.2013.09.006
一种构造正则表达式更小ε-NFA的方法
基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用,提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理,然后构造每个分片的NFA,最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下,能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.
正则表达式、有限自动机、闭包、同态运算、构造算法
34
TP301.1(计算技术、计算机技术)
国家自然科学基金资助项目61100021,61121061,61202447;河北省自然科学基金资助项目F2012501014;教育部高等学校博士学科点专项科研基金资助项目20120042120009;河北省自然科学青年基金资助项目F2013501048
2015-07-29(万方平台首次上网日期,不代表论文的发表时间)
共4页
1240-1243