TY - JOUR AU - Syzdykov, Mirzakhmet PY - 2022/12/29 Y2 - 2024/03/28 TI - Equivalence of Complexity Classes via Finite Automata Derivatives JF - ADVANCED TECHNOLOGIES AND COMPUTER SCIENCE JA - atcs VL - 1 IS - 4 SE - Artificial intelligence technologies DO - UR - https://atcs.iict.kz/index.php/atcs/article/view/105 SP - 9-14 AB - <p>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</p> ER -