Chiang Mai Journal of Science

         Several techniques like Thompson’s construction, partial derivatives, follow automata and positional automata have been proposed for the conversion of regular expressions to non-deterministic finite automata. Researchers have proposed different methodologies for the conversion of parallel regular expressions to non-deterministic finite automata having the number of states O(2^|r|). The aim of the paper is to propose a new approach for the conversion of parallel regular expressions to non-deterministic finite automata. This innovative approach is the generalization of the Antimirov partial derivatives for the conversion of regular expressions to e-free non-deterministic finite automata. The number of states of the non-deterministic finite automaton is reduced from exponential O(2^|r|) to polynomial (O(m^k+1)), using this novel approach.