Extended Regular Expressions in Finite Automata Revisited

Abstract

While the past work was focused on limited set of regular expressions (RE) within extended operators like intersection, complement and subtraction (ERE), in this article we extend the definition of RE for zero-width operators like Kleene closure. For this purpose the tagged states are implemented within the space of states of the non-deterministic finite automata (NFA) as well as for modified subset construction of deterministic finite automata (DFA). The prior research is good for extended operators, however, empty words play vital role even in extended regular expression matching as well as for typical regular expressions. Thus, the tagged states and transitions are introduced as well as the local search, which was first developed for approximate back-reference matching and now is suitable for extended operators. Thus, the linear complexity isn't avoided and is obtained for the general case of the grammars of regular expressions. It's also shown that the limited set of grammar rules for regular expressions are the good idea to obtain preliminary results for further generalization using algorithmic paradigms.