ARTÍCULO
TITULO

Automata ? complete invariants for strongly connected regular languages

Boris Melnikov    

Resumen

In this paper, we continue to consider strongly coupled automata, as a subset of ordinary nondeterministic finite automata. Based on this, strongly related regular languages are naturally defined. We consider some properties of the concept of the strong connectedness, in particular, the non­closure of this class with respect to ordinary set­theoretic operations. The title of the paper includes the word ?invariants?; such ones for the regular languages are not only the canonical automata (besides, they are complete invariants), but also the canonical automaton for the mirror language, as well as the basis and universal automata, which ones (for strongly connected languages) are the main subject of this paper. One of the important incomplete invariants is the binary relation #, which is also discussed in this paper. We show the connection of the concept of ?strong connectedness? with the basic and universal finite automata. Thus, for a strongly connected language, the basic automaton is not necessarily strongly connected, and the universal automaton is necessarily so. We consider the last fact to be the most important result related to strongly connected languages: it allows us to equivalently reformulate the definition of a strongly connected regular language, such can be considered a language for which its universal automaton is strongly connected. We illustrate the consideration of basis and universal automata for strongly connected languages with some examples, the consideration of which was started in the previous paper on strongly connected languages.

PÁGINAS
pp. 1 - 10
REVISTAS SIMILARES

 Artículos similares