Pseudo-automata for generalized regular expressions

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we introduce a new formalism which is intended for representing a special extensions of finite automata. We call them generalized nondeterministic finite pseudo-automata. This formalism gives not only the equivalence between two classes of finite automata, i.e., ordinary nondeterministic finite automata and pseudo-automata introduced by us, which also define all the regular languages. This formalism also gives an opportunity of defining the complement operation (and, therefore, generalized regular expressions) in a way similar to the usual “automata” methods. We use the term “pseudo-automata”, because, unlike usual automata constructions (ordinary nondeterministic finite automata, push-down automata, Turing machines etc.), we do not indicate the concrete paths for defining the considered word of the given regular language; the introduced formalism gives only the algorithm for answering the question, whether the given word belongs to the considered language. In the paper, we firstly give definition of the pseudo-automata and their languages. After that, we consider the diagrams allowing to visualize them and give some examples. Then we consider some properties of introduced formalism.


Full Text:

PDF

References


Kirsten D. and Maurer I. On the determinization of weighted automata.

Journal of Automata, Languages and Combinatorics. 2005, vol. 10, no. 2/3. pp. 287-312.

Kirsten D. Distance desert automata and the star height problem.

Informatique Theorique et Applications. 2005, vol. 39, no. 3. pp. 455-509.

Melnikov B. and Vakhitova A. Some more on the finite automata.

The Korean Journal of Computational and Applied Mathematics.

, vol. 5, no. 3. pp. 495-506.

Melnikov B. Extended nondeterministic finite automata.

Fundamenta Informaticae. 2010, vol. 104, no. 3. pp. 255-265.

Vylitok A., Zubova M. and Melnikov B. Ob odnom rasshirenii klassa konechnyh avtomatov ... [About one extension of the class of finite automata for accepting context-free languages].

Vestnik of Moscow University. Series 15: Computational mathematics and cybernetics. 2013, no. 1. pp. 39-45. (in Russian)

Baumgartner S. and Melnikov B. Obobschennye nedeterminirovannye konechnye avtomaty [Generalizing nondeterministic finite automata].

Izvestiya of Higher Educational Institutions. Volga Region. Phisical and Mathematical Sciences, 2013, no. 2 (26), pp. 64-74. (in Russian)

Salomaa A. Jewels of Formal Language Theory. Computer Science Press, 1981, 144 p.

Hromkovic J. Theoretical Computer Science. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer, 2003. 321 p.

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

Brauer W. Automatentheorie. Eine Einfuhrung in die Theorie endlicher Automaten. Stuttgart: B. G. Teubner, 1984, 493 S. (in German)

Melnikov B. and Melnikova A. Edge-minimization of non-deterministic finite automata. The Korean Journal of Computational and Applied Mathematics. 2001, vol. 8, no. 3. pp. 469-479.

Melnikov B. and Melnikova A. Mnogoaspektnaya minimizaciya nedeterminirovannyh konechnyh avtomatov ... [Multi-aspect minimization of nondeterministic finite automaton (Part I. Auxiliary facts and algorithms)]. Izvestiya of Higher Educational Institutions. Volga Region.

Phisical and Mathematical Sciences, 2011, no. 4, pp. 59-69. (in Russian)

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

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

Melnikov B. and Sayfullina M. O nekotoryh algoritmah ekvivalentnogo preobrazovaniya nedeterminirovannyh konechnyh avtomatov [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)


Refbacks

  • There are currently no refbacks.


Abava   MSU conference 2018

ISSN: 2307-8162