INFORMATICA

Informatica

0868-49520868-4952

INF13304

10.3233/INF-2002-13304

Research article

A New Algorithm of Constructing the Basis Finite Automaton^✩

Melnikov

Boris

bormel@mail.ruMelnikova

Alexandra

avahi@mail.ruDepartment of Mechanics and Mathematics, Simbirsk State University, L. Tolstoy str. 42, 432700 Simbirsk, RussiaDepartment of Economics, Dimitrovgrad Branch of Simbirsk State University, Dimitrov str. 4, 433510 Dimitrovgrad, Russia

^✩

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

01012002

13329931001012002

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.

Keywordsregular languagesbasis finite automata