Some more on the equivalent transformation of nondeterministic finite automata. Part II. The "deleting" algorithm

Boris Melnikov

Abstract


This paper is a continuation of our following previous papers, where we considered some simple algorithms for combining states of the given nondeterministic finite automaton, the reduction some problems related to the star-height to considering automata, and possible classification 
of the states and loops of the given automaton. In this part of the paper, we shall describe an algorithm which deletes the state of a given nondeterministic finite automaton. This algorithm preserves basic properties of automata, i.e. the languages of the given and the obtained automata are the same, and the value of star-height for the obtained automaton is no more than such value for the given automaton. Like Part I, we consider two states having the same values of the state marking functions. Then we could apply the same algorithms, but, generally speaking, in the case of the initial conditions considered in this part, the application of combining algorithm of previous part increases the value of star-height of the automaton under consideration. Then we should apply another algorithm, we consider such algorithm in this part. We call it by deleting algorithm, because it deletes a state; however, we not only delete a state, but sometimes add some edges, inputs and outputs before deleting. We also consider some examples of using the described deleting algorithm.


Full Text:

PDF

References


Melnikov B. An approach to the classification of the loops of finite automata. Part I: Long corresponding loops //International Journal of Open Information Technologies. 2019, vol. 7, no. 4, pp. 1–5.

Melnikov B., Melnikova A. Some properties of the basis finite automaton //The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2002, vol. 9, no. 1. pp. 135–150.

Melnikov B., Sayfullina M. On some algorithms for the equivalent transformation of nondeterministic finite automata //Izvestiya of Higher Educational Institutions. Mathematics. 2009, no. 4, pp. 67–72. (in Russian, https://elibrary.ru/item.asp?id=11749888)

Melnikov B. Extended nondeterministic finite automata //Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 255–265.

Melnikov B. The star-height of a finite automaton and some related questions //International Journal of Open Information Technologies. 2018, vol. 6, no. 7, pp. 1–5.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part II: The classification of the states based on the loops //International Journal of Open Information Technologies. 2018, vol. 6, no. 11, pp. 1–6.

Melnikov B., Melnikova A. Pseudo-automata for generalized regular expressions //International Journal of Open Information Technologies. 2018, vol. 6, no. 1, pp. 1–8.

Harary F. Graph Theory. Addison Wesley (Boston), 1969, 274 p.

Aho A., Ullman J. The Theory of Parsing, Translation, and Compiling, Vol. 1: Parsing. Prentice Hall (NJ), 1972, 560 p.

Melnikov B., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language //The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2002, vol. 9, no. 2. pp. 475–485.

Polak L. Minimizations of NFA using the universal automaton //International Journal of Foundations of Computer Science. 2005, vol. 16, no. 5. pp. 999–1010.

Lombardy S., Sakarovitch J. The Universal Automaton //Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press. 2008, vol. 2, pp. 457–504.

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems //Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 267–283.

Melnikov B. The complete finite automaton //International Journal of Open Information Technologies. 2017, vol. 5, no. 10, pp. 9–17.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162