Novel NFA engine construction method of regular expressions

Abstract

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 NFAp with only one start state and one final state can be obtained by using PFA construction method.NFAphave 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 NFApis one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal.

Keywords

• deep packet inspection
• pattern matching
• regular expression
• finite automata
• construction algorithm