After that, we considered the algorithm for verifying the implementation of the coverage relation, and identified the auxiliary objects used to prove the correctness of this algorithm. The covering relation), the double use of which is equivalent to the use of the equivalence relation at infinity. We have formulated a simpler binary relation in a variety of languages (i.e. Automata c Theodore Norvell, Memorial University Finite State Automata Defn: A nite state automaton (FSA), A (V,E,s,F,) consists of (V,E,) is a nite directed graph sVis a start state FVis a set of nal states is a set of input symbols (events)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 nonempty finite languages); this is so called equivalence relation at infinity.
The main idea of the proof of the fact, that the algorithm for constructing a finite automaton for checking the equality of infinite iterations of two finite languages is polynomial is as follows. We introduce a completely different object (i.e., a simplified primary automaton, NSPRI), which also describes the construction of an iterative morphism tree, but is defined not on sets of words, but on words. After that, we define some variants of special nondeterministic automata corresponding to it, describing in fact the construction of this iterative morphism tree. It is deterministic, defined on sets of words, and each of these sets is a subset of the set of prefixes of the second of the given languages. We have defined a specific such automaton for two given finite languages; this is so called primary automaton, PRI. In the infinite iterative trees considered, we combine the equivalent states, obtaining in fact a deterministic finite automaton.
We solve this problem by requiring that the resulting nondeterministic automaton be an analog of the total deterministic automaton.A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical. Therefore, we construct a nondeterministic automaton defined simply on the set of possible prefixes; at the same time, there is some question related to when exactly this automaton gives a positive result. However, in doing so, we are working with many sets of possible prefixes, which makes it impossible for the algorithm to be polynomial.
5–13 (in Russian).Melnikov B Variants of finite automata corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. Melnikov B Variants of finite automata corresponding to infinite iterative morphism trees. Mathematics and Computer Science Division, Argonne National laboratory. System for implementing concurrent, hierarchical, finite state machines.
Minimizations of NFA using the universal automaton // International Journal of Foundation of Computer Sciences. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. ?–? (in Russian).Kameda T., Weiner P.
From the theory to the practical algorithms // Bulletin of the Voronezh State University. Building a universal finite automaton. 194–201.Dolgov V., Melnikov B. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // In: Proceedings – 5th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP–2012. 67–72 (in Russian).Melnikov B., Tsyganov A. On some algorithms for equivalent transformation of nondeterministic finite automata // News of higherEducational institutions.
An approach to algorithmizing the problem of vertex minimization of nondeterministic automata. 78–85 (in Russian).Abramyan M., Melnikov B. Examples of how algorithms work // Bulletin of the Voronezh State University. Building a universal finite automaton.
Steklov Mathematical Institute. Theory of algorithms (Proceedings of the V. Krasnoyarsk Science and Technology City Hall of the Russian Union of Scientific and Engineering Associations.
Mathematical Foundations of Automata Theory. 30–33 (in Russian).Pin J.E. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. (in Russian).Alekseeva A., Melnikov B. (in Russian).Skornyakov L. Mathematical logic and theory of algorithms.
0 kommentar(er)
