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

Authors

Keywords:

regular expression, membership problem, extended operators, linear algorithm

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.

Downloads

Download data is not yet available.

Author Biography

Mirzakhmet Syzdykov, al-Farabi Kazakh National University, Almaty, Kazakhstan

Born 11/09/84. 2006-2009, aspirant at Institute of Problems in Informatics and Control

Downloads

Published

2021-12-20

How to Cite

Syzdykov, M. (2021). Membership Problem in Non-deterministic Finite Automata for Extended Regular Expressions in Linear Polynomial Time. ADVANCED TECHNOLOGIES AND COMPUTER SCIENCE, 1(4), 14–17. Retrieved from https://atcs.iict.kz/index.php/atcs/article/view/71

Issue

Section

Applied mathematics, computer science and control theory