ARTÍCULO
TITULO

An approach to the classification of the loops of finite automata. Part II: The classification of the states based on the loops

Boris Melnikov    
Aleksandra Melnikova    

Resumen

In this paper, we considered questions of the possible classification of the states and loops of a nondeterministic finite automaton.For the development of algorithms for equivalent transformation of nondeterministic finite automata, we consider the basis finite automaton for the given regular language and the paths and loops of its transition graph. We also consider the paths and loops of the transition graph of another nondeterministic automaton that defines the same language. On the basis of this, we define corresponding paths and loops of two mentioned automata and the questions of their classification. This classification gives, for example, the possibilities for describing some heuristic algorithms for minimization of nondeterministic automata. For the last thing, we describe the following objects. For each state of the basis automaton, we consider the states of the given automaton corresponding to this state of the basis automaton, and give their classification as a function of the loops passing through the same state of the basis automaton. Their subset is the set of so-called including loops, on the basis of which we determine so-called partially complete loops. For any chosen vertex of the basic automaton, we call the vertices of the considered nondeterministic automaton, through which all possible partially complete loops pass, by complete cyclic states. At the end of the paper, we formulate the hypothesis that if for any state of the considered nondeterministic automaton, there exists at least one corresponding state of the basis automaton, such that the first one is a complete cyclic state for the second one, then all the corresponding states of the basis automaton are such ones.In the presented Part II of the paper, we are considering issues of a special classification of states of any nondeterministic finite automaton. This classification is based on the application of developed in the first part of this paper classification of the loops.

 Artículos similares

       
 
Boris Melnikov     Pág. 1 - 4
This paper is a continuation of two previous parts. In them, we considered some simple algorithms for combining and removing (deleting) states of the given nondeterministic finite automaton, as well as the reduction some problems related&n... ver más

 
Tze Lin Kok     Pág. 33
Modern chemical plants consist of a large number of process units that have hundreds of control loops.  As one of the most important elements of a control loop, control valves are essential assets to the plant because they ensure the high quality of... ver más

 
Boris Melnikov,Aleksandra Melnikova     Pág. 9 - 14
In this paper, we considered questions of the possible classification of the states and loops of a nondeterministic finite automaton. For the development of  algorithms for equivalent transformation of nondeterministic finite automata, we consider t... ver más