Novel NFA engine construction method of regular expressions
A novel method for constructing smaller non-deterministic finite automata (NFA) engine from given regular expressions named PFA was proposed.There are three main algorithms in PFA,the pretreatment algorithm,the coding parser tree algorithm and the NFA construction algorithm based on the coded binary...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2014-10-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.10.012/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850122542469087232 |
|---|---|
| author | Mao-hua JING Yi-xian YANG Tao WANG Yang XIN |
| author_facet | Mao-hua JING Yi-xian YANG Tao WANG Yang XIN |
| author_sort | Mao-hua JING |
| collection | DOAJ |
| description | A novel method for constructing smaller non-deterministic finite automata (NFA) engine from given regular expressions named PFA was proposed.There are three main algorithms in PFA,the pretreatment algorithm,the coding parser tree algorithm and the NFA construction algorithm based on the coded binary tree.The smaller NFA named NFA<sub>p</sub> with only one start state and one final state can be obtained by using PFA construction method.NFA<sub>p</sub>have linear size in terms of the size of given regular expressions.It is the smallest NFA comparing with current methods like Thompson NFA,follow automata,position automata and partial derivatives automata.The size of NFA<sub>p</sub>is one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal. |
| format | Article |
| id | doaj-art-5cc9cb9b9cbf41208175a82be0418f5a |
| institution | OA Journals |
| issn | 1000-436X |
| language | zho |
| publishDate | 2014-10-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-5cc9cb9b9cbf41208175a82be0418f5a2025-08-20T02:34:49ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2014-10-01359810659686736Novel NFA engine construction method of regular expressionsMao-hua JINGYi-xian YANGTao WANGYang XINA novel method for constructing smaller non-deterministic finite automata (NFA) engine from given regular expressions named PFA was proposed.There are three main algorithms in PFA,the pretreatment algorithm,the coding parser tree algorithm and the NFA construction algorithm based on the coded binary tree.The smaller NFA named NFA<sub>p</sub> with only one start state and one final state can be obtained by using PFA construction method.NFA<sub>p</sub>have linear size in terms of the size of given regular expressions.It is the smallest NFA comparing with current methods like Thompson NFA,follow automata,position automata and partial derivatives automata.The size of NFA<sub>p</sub>is one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal.http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.10.012/deep packet inspectionpattern matchingregular expressionfinite automataconstruction algorithm |
| spellingShingle | Mao-hua JING Yi-xian YANG Tao WANG Yang XIN Novel NFA engine construction method of regular expressions Tongxin xuebao deep packet inspection pattern matching regular expression finite automata construction algorithm |
| title | Novel NFA engine construction method of regular expressions |
| title_full | Novel NFA engine construction method of regular expressions |
| title_fullStr | Novel NFA engine construction method of regular expressions |
| title_full_unstemmed | Novel NFA engine construction method of regular expressions |
| title_short | Novel NFA engine construction method of regular expressions |
| title_sort | novel nfa engine construction method of regular expressions |
| topic | deep packet inspection pattern matching regular expression finite automata construction algorithm |
| url | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.10.012/ |
| work_keys_str_mv | AT maohuajing novelnfaengineconstructionmethodofregularexpressions AT yixianyang novelnfaengineconstructionmethodofregularexpressions AT taowang novelnfaengineconstructionmethodofregularexpressions AT yangxin novelnfaengineconstructionmethodofregularexpressions |