Search

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. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we continue our study on the state complexity of combined operations on regular languages. We study the state complexities of , , , and , for regular languages , , . We obtain the exact bounds for these combined operations and show that the state complexities of and are the same as the mathematical compositions of the state complexities of their component individual operations, while, on the other hand, the state complexities of and are lower than the corresponding mathematical compositions. [Copyright &y& Elsevier]

Abstract: Several methods have been developed to construct -free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a -free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods. [Copyright &y& Elsevier]