Equivalence of Complexity Classes via Finite Automata Derivatives

Abstract

In this article practical, experimental and theoretical results of the conducted research are presented, these results refer to the main question in complexity theory like the “P versus NP” theorem, first proposed by Stephen Cook in his seminal paper, we give concise question of the equivalence of these classes from the state of conversion algorithm of non-deterministic finite automata (NFA) to deterministic finite automata (DFA), we do it by considering the canonical regular expression form presented by Schneider Klaus and do the derivative processing from the Berry-Sethi algorithm, the result gives P-complete algorithm along the canonical form of regular expressions when applying subset construction for specific regular expressions or NFA, DFA in this case remains applicable even for Turing tape machines, however, due to the past statement of the “P versus NP” theorem given by author in previous work this leads to the conclusion of the equivalence of complexity classes like P and NP as in canonical form the subset construction produces exponential growth of the number of states of DFA