Redirigiendo al acceso original de articulo en 20 segundos...

Variants of finite automata corresponding to infinite iterative morphism trees. Part I

Boris Melnikov    


Quite briefly, the subject of this paper can be formulated as follows: in the previously considered infinite iterative morphism trees, we combine equivalent states, obtaining in fact a deterministic finite automaton; after that, we investigate some properties of this automaton. In more detail, we work with various variants of finite automata, each of which corresponds to some infinite iterative tree of the morphism under consideration. In this case, the automata constructed for different morphisms describe the main properties of the given morphisms. In addition, in each case (i. e., for each variant of the automaton), the following ?inverse problem? also arises: to describe a morphism (or simply specify a pair of languages) for which some given automaton is obtained. In addition, the paper describes the possible connection of the material under consideration with problems arising in other areas of the theory of formal languages. Among the variants of automata corresponding to an infinite iterative morphism tree for a given ordered pair of finite languages, we first define the socalled primary automaton. It is deterministic, defined on sets of words, and each of these sets is a subset of the set of suffixes of the second of the given languages. Next, we consider several variants of nondeterministic automata corresponding to it. After that, we introduce a completely different object, i. e., a simplified primary automaton defined not on sets of words, but on words. Despite the significant difference with automata built on sets of words, all constructions for specific examples of languages can be performed using the same computer program. Next, we consider the features that appear when applying algorithms that form finite automata to pairs of matching languages. At the end of the paper, we briefly formulate the directions for further work related to the issues discussed in it. In this Part I, we consider deterministic automata only.

 Artículos similares

Tatiana Generalova     Pág. 1 - 4
A new formalism for the   specification  of context-free languages is   presented.  In this formalism, a generalization of the class of nondeterministic finite automata can be obtained by using an auxiliary alphabet and imposing addit... ver más

Boris Melnikov     Pág. 1 - 10
In our previous publications, we considered a simplified version of the definition of omega-automata that define omega-languages compared to the classics. However, despite this ?simplification?, such a definition makes it possible to specify the subclass... ver más

Boris Melnikov,Aleksandra Melnikova     Pág. 1 - 10
In this paper, we continue the topic related to the special binary relation on the set of formal languages (considered primarily on the set of iterations of non­empty finite languages); this is so called equivalence relation at infinity. We have formulat... ver más

S. A. Zhucov     Pág. 28 - 38
The article discusses an invasion model in the form of memory destruction of one type of abstract algorithm executor introduced by Schönhage. Two invasion scenarios are defined (attack without aftereffect and attack with aftereffect), and the macros prop... ver más

Mikhail Abramyan,Boris Melnikov     Pág. 1 - 9
We continue to study heuristics that can be applied to solve the problem of minimizing the states of nondeterministic finite automata by the branch and bound method, or rather, to the implementation of the most difficult stage of the solution associated ... ver más