A New Algorithm of Constructing the Basis Finite Automaton

Article type: Research Article

Authors: Melnikov, Boris^; | Melnikova, Alexandra

Affiliations: Department of Mechanics and Mathematics, Simbirsk State University, L. Tolstoy str. 42, 432700 Simbirsk, Russia. E-mail: [email protected] | Department of Economics, Dimitrovgrad Branch of Simbirsk State University, Dimitrov str. 4, 433510 Dimitrovgrad, Russia. E-mail: [email protected]

Note: [] The first author was partially supported by the Russian Foundation of the Basic Research (project No. 00-15-99253).

Abstract: In this paper we consider non-deterministic finite Rabin–Scott's automata. We obtain some properties for the basis automaton, which is, like automaton of canonical form, an invariant of a given regular language. We obtain also a new algorithm of constructing the basis automaton for a given regular language.

Keywords: regular languages, basis finite automata

DOI: 10.3233/INF-2002-13304

Journal: Informatica, vol. 13, no. 3, pp. 299-310, 2002