Menu: Home :: go to Journal :: switch to Russian :: switch to English
You are here: all Journals and Issues→ Journal→ Issue→ Article

USING THE STATE-MARKING FUNCTIONS WHEN WORKING WITH THE CYCLES OF THE BASIS FINITE AUTOMATON

Annotation

We consider in this paper the basis finite Rabin-Scott’s automaton defined earlier by the author and used to solve various problems in the theory of regular languages, in particular, to minimize finite automatons tasks by various criteria. For the basis automaton, the color of the edges is defined by using injective function. Different ways and cycles of the transition graph of the basis automaton corresponding to the ways and cycles of the transition graph of some automaton possibly defining a given regular language are explored. With the help of generalized state-marking functions, an algorithm for adding an edge in non-deterministic finite automaton is formulated.

Keywords

nondeterministic finite automaton; basis automaton; algorithms of equivalent transformation; state-minimization; edge-minimization; state-marking functions

Full-text in one file

Download

UDC

517.713

Pages

1310-1312

References

1. Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. 1999. Vol.6. № 2. P. 277-290. 2. Vakhitova A. The basis automaton for the given regular language // The Korean Journal of Computational and Applied Mathematics. 1999. Vol.6. № 3. P. 617-624. 3. Mel'nikova A.A. Bazisnye avtomaty v reshenii problemy optimizacii // Vestnik Tambovskogo universiteta. Serija Estestvennye i tehnicheskie nauki. Tambov, 2007. T 12. Vyp. 4. S. 492-494. 4. Mel'nikov B.F., Mel'nikova A.A. Mnogoaspektnaja minimizacija nedeterminirovannyh konechnyh avtomatov. Chast' I. Vspomogatel'nye fakty i algoritmy // Izvestija vuzov. Povolzhskij region. Fiziko-matematicheskie nauki. 2011. № 4 (20). S. 59-69. 5. Mel'nikov B.F., Mel'nikova A.A. Mnogoaspektnaja minimizacija nedeterminirovannyh konechnyh avtomatov. Chast' II. Osnovnye algoritmy // Izvestija vuzov. Povolzhskij region. Fiziko-matematicheskie nauki. 2012. № 1 (21). S. 31-43.

Received

2015-06-11

Section of issue

Scientific articles

Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.