Some More on the Modeling Context-Free Languages by Nondeterministic Finite Automata

Tatiana Generalova


A new formalism for the   specification  of context-free languages is   presented.  In this formalism, a generalization of the class of nondeterministic finite automata can be obtained by using an auxiliary alphabet and imposing additional conditions.  Received  mechanism, so-called bracketed automata,  can be used  for  recognizing context-free languages. At the same time  this formalism   is   similar to  the nondeterministic finite automata and this fact allows using classic algorithms of the equivalent transformation of nondeterministic finite automata for objects of formalism that specifies the context-free languages. An algorithm for constructing a bracketed automaton according to the given context-free grammar is considered. An important problem that arises in the design and practical implementation of automation systems for constructing translators are optimization issues; we mean here both of the compilers themselves and of the generated executable code. To obtain optimized variants of translators, different methods are used in practice; one of them is to obtain various equivalent descriptions of the compiled language.  In most situations, when developing compilers, we need to use context-free languages  or some related constructions. In some cases, the formalism we have described makes it possible  to construct a minimal object from the point of view of the number of states that describes the special extension of the class of finite automata.

Full Text:



Aho A., Ullman J. “The theory of parsing, translation and compiling”, V.1, Prentice-Hall, INC, Englewood Cliffs, N. J., 1972, pp. 1002.

Vylitok A., “On a pushdown automata graph construction”, Vestnik of Moscow University, S. 15, Computational Mathematics and Cybernetics, 1996, no. 3, pp. 68–73 (in Russian).

Vylitok A., Zubova M., Melnikov B. “On an extension of the class of finite automata for the specification of context-free languages”, Vestnik of Moscow University, S. 15, Computational Mathematics and Cybernetics, 2013, no. 1, pp. 39–45 (in Russian).

Wirth N. “Compiler Construct”, M.: DMK-Press, 2013, pp. 193.

Wirth N., Gutknecht J., “Porject Oberon. The design of an operating system and compiler”. 2005, pp. 441.

“Some more on the finite automata”, Melnikov B.F., Vakhitova A.A. Journal of Applied Mathematics and Computing, 1998, V. 5, no. 3, pp. 495-505.

Melnikov B.F., Melnikova A.A., “Some properties of the basis finite automaton”, Korean Journal of Computational and Applied Mathematics,

, V.9, no.1, pp. 135-150.

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

Melnikov B., Sayfullina M., “On some algorithms of equivalent transformations of nondeterministic finite automata”, Izvestiya of universites, Mathematics. 2009, no.4, pp.67-72 (in Russian), (English translation: Mel’nikov B., Sayfullina M., Some algorithms for equivalent transformations of nondeterministic finite automata. Russian Mathematics, (Izv.VUZ). 2009, no. 4, pp. 54-56.)

Melnikov B., “Extended nondeterministic finite automata”, Fundamenta Informaticae, 2010, V. 104, no. 3, pp. 255-265.

Dolgov V., Melnikov B., “The construction of a universal finite automaton. Part I: From theory to practical algorithms”. Vestnik of Voronezh State University, S: Physics. Mathematics, 2013, no. 2. pp. 173-181 (in Russian).

Generalova T., Melnikov B., Vylitok A., “On the extension of the finite automata class for context-free languages specification”, International Journal of Open Information Technologies, 2018, V.6, no.8, pp.1-8. (

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

Wirth N. “Algorithms + Data Structure = Programs”, Prentice-Hall PTR UPPER Saddle River, N.J., USA, 1978.

Grogono P., “Programming in Pascal”, 1982, M.: Mir, pp. 378.


  • There are currently no refbacks.

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

ISSN: 2307-8162