Postfix automata

We introduce a notion of postfix automata and apply it to finite automata constructions. We give a compact method for constructing smaller nondeterministic finite automata (NFAs) from given regular expressions. There are four steps in our method. First, we convert one or more given regular expressions into postfix form, better known as Reverse Polish notation, and call it a postfix regular expression. Second, we construct a syntax tree for the postfix regular expression. Next, we code the syntax tree using a specific algorithm and finally, we construct an NFA based on the coded syntax tree. Using our method we can obtain smaller NFAs, called postfix automata, with only one starting state and one final state. In this paper, we prove several notions and present a classical example to compare the size of a postfix automaton with the NFAs created by several classical construction methods. We also derive the efficiency in reducing the size of the NFA through general theoretical analysis.

Authors

• Maohua Jing
• Yixian Yang
• Ning Lu Huawei Technologies Co., Ltd
• Wenbo Shi
• Changyong Yu

Keywords

• Regular expression
• Finite automata
• Follow automata
• Thompson's automata