Membership Problem in Non-deterministic Finite Automata for Extended Regular Expressions in Linear Polynomial Time

Abstract

The recent work on implementing regular expression (RE) matching or membership problem solution for extended operators (ERE) like intersection, complement and subtraction gave exponential results on the size of input. As our previous result was focused on deterministic finite automata (DFA) for extended regular expressions, we present the new linear algorithm for ERE matching on non-deterministic finite automata (NFA) with the help of De Morgan’s law to re-write the expression in exceptional order so that the conditional matching satisfies the correctness of the matching algorithm on NFA. We also prove that the proposed methodology is correct within the extensions of NFA like logical states as it was done before for DFA in the prior scientific work. We will also show how to implement these logical states in NFA using typical constructions like Thompson’s. The proof of linear working time is also given which is obvious due to the re-writing rules for correct implementation. The important role of concatenation operator over extended constructions is also shown. The algorithm working time is O(m*n), where m is the size of expression and n is the size of matching word.