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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1000-436X |