Extended basis finite automaton. Part II. Description of auxiliary languages and some properties

Boris Melnikov, Aleksandra Melnikova

Abstract


In the second part of this paper, we continue to consider a special extension of the class of nondeterministic finite automata. We show by examples the following fact: there are regular languages, in the basis automata of which, some vertices do not have loops corresponding to the loops of the corresponding vertices of other equivalent automata; however, precisely such loops do exist at similar vertices of extended basic automata. We also continue to consider the extended basic finite automaton. We prove that for such an automaton, all auxiliary languages obtained in the constructions are regular; this fact is the main subject of Part II. All of the above allows us to simplify the definition of the extended basic automaton. In addition, we show the possibility of using extended finite automata for proving statements related to "ordinary" nondeterministic finite automata, as well as the inverse possibility of using "ordinary" automata to prove statements related to extended basic automata. At the end of the paper, we describe the possibilities of applying this formalism, in particular, the use of extended automata in algorithms for minimizing non-deterministic finite automata.

Full Text:

PDF (Russian)

References


Melnikov B., Melnikova A. Extended basis finite automaton. Part I. The basic definitions // International Journal of Open Information Technologies. – 2018. – Vol. 7. No. 10. – P. 1–8.

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. – P. 135–150.

Melnikov B., Vakhitova A. Some more on the finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 1998. – Vol. 5. No. 3. – P. 495–506.

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. – P. 475–485.

Melnikov B. Regular languages and nondeterministic finite

automata // Moscow: Russian State Social University Ed., 2018. – 180 p. (in Russian)

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. – 2010. – Vol. 104. No. 3. – P. 267–283.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part I: Long corresponding loops // International Journal of Open Information Technologies. – 2018. Vol. 6. No. 9. – P. 9–14.

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. – P. 1–6.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 10. – P. 9–17.

Melnikov B., Melnikova A. Edge-minimization of ondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2001. – Vol. 8. No. 3. – P. 469–479.

Melnikov B., Sayfullina M. On some equivalent ransformation algorithms for nondeterministic finite automata // Higher ducation News. Mathematics. – 2009. – No. 4. – P. 67–72. (in Russian)

Melnikov B. Extended nondeterministic finite automata // Fundamenta Informaticae. – 2010. – Vol. 104. No. 3. – P. 255– 265.


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162