This article is cited in 1 paper

Mathematics

Multi-aspect minimization non-deterministic finite automata (Part I. Supporting facts and algorithms)

B. Melnikov^a, A. A. Melnikova<sup>b

a</sup> Tolyatti State University, Tolyatti
^b Dimitrovgrad branch of Ulyanovsk State University, Dimitrovgrad

Abstract: In the first part of the article, the authors consider some auxiliary algorithms for two problems of minimization of nondeterministic finite automata: vertex-minimization and edge-minimization. The researchers give a simple algorithm for minimization of deterministic automata, which also enables simultaneous construction of state-marking functions. The article proves some auxiliary propositions about input languages of the basis automaton states, necessary for algorithms of equivalent transformation of nondeterministic finite automata.

Keywords: nondeterministic finite automaton, basis automaton, algorithms of equivalent transformation, state-minimization, edge-minimization.

UDC: 519.178