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 algo-rithm 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. NFAp 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 NFAp is one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal.