Design and Development of Algorithms for Converting Parallel Regular Expressions to Deterministic Finite Automata

Abstract

Regular expressions are widely used in various applications such as XML schema languages, compiler designs, model checking, bio-informatics, virus detection systems, intrusion detection systems, finite state based testing, text processors and as a programming tool for multifarious scripting languages such as PHP and PERL, etc. A regular expression extended by intersection and shuffle operators do not increase the expressive power of the regular expression, but succinctness due to the inclusion of these additional operators are difficult to handle with the standard operators. In one form or another, the additional operator shuffle appears in different forms of computer science, namely process algebra, multipoint communication, XML schema RELAX NG, computational resource reduction, and concurrency of processes. This dissertation focuses on the design of algorithm’s for the conversion of regular expressions with additional operators to the finite automaton. Firstly, we develop an algorithm for the conversion of parallel regular expressions to non- deterministic finite automata using the follow-position of symbols presenting in the parallel regular expressions. It has also been proven that parallel regular expressions cannot be converted into deterministic finite automata directly. In the worst-case scenario, 2m+1 number of states are required for the construction of the non- deterministic finite automaton, where m represents the number of instances of alphabets in a parallel regular expression. In earlier existing approaches, the number of states of the non-deterministic finite automaton in the worst case is equal to 22jrj..3C, where jrj and C represent respectively the length and number of concatenation in a parallel regular expression. Secondly, we explore and design a sound and complete algorithm for the conversion of semi-extended regular expressions to deterministic finite automata. Comparison demonstrates that the deterministic finite automaton generated using the proposed algorithm is smaller than the earlier existing approaches in the literature. The proposed method is an extension of the direct conversion of regular expressions to deterministic finite automata. Finally, we develop an algorithm for the metamorphosis of parallel regular expressions to the right linear grammar. The metamorphosis of parallel regular expressions to right linear grammar gives a prescript of reduction in concurrency. The novelty of the algorithm is the use of follow-position of symbols for the metamorphosis of parallel regular expressions to regular grammar.