On the extension of the finite automata class for context-free languages specification

Tatiana Generalova, Boris Melnikov, Alexey Vylitok


In this paper, a new formalism for specification of context-free languages is proposed. In this formalism, the application of an auxiliary alphabet and the imposition of additional conditions make it possible to obtain an extension of the class of nondeterministic finite automata. This approach allows to receive a mechanism that recognizes context-free languages. Despite the fact that we define the class of context-free languages, this formalism is similar to the nondeterministic finite automata. This circumstance allows to use classic algorithms of the equivalent transformation of nondeterministic finite automata for objects of formalism that specifies the context-free languages. As such a formalism, automata of a special kind, so called bracketed automata, are introduced. In this paper, we consider the algorithm for constructing a bracketed automaton according to the given context-free grammar. We give an example of a context-free grammar with iterations for the model of arithmetic expressions.
Then we consider some equivalent transformations of bracketed automata. We introduce a new special alphabet and prove that on the basis of the alphabet, for each bracketed automaton the usual nondeterministic finite automaton can be constructed. Vise versa, for each nondeterministic finite automaton over a new alphabet, it is possible to construct an equivalent bracketed automaton. Everything done in the paper makes it possible to apply various algorithms of equivalent transformations of nondeterministic finite  automata, such as constructing of a minimal automata, universal automaton, etc., and obtain objects of the proposed formalism which are more acceptable in terms of some characteristics, for example, with fewer numbers of the vertices or the edges.

Full Text:



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

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

Ollongren A. "Definition of programming languages by interpreting automata", (London: Academic Press, 1974).

Stanevichene L. "On one way of studying contextless languages", The Cybernetics, 1989, no. 4, pp. 135-136.

Staneviciene L. "D-Graphs in Context-Free Language Theory", Informatica (Journal of Lithuanian Academy of Sciences), 1997, V.8, no. 1. pp. 43-56.

Stanevichene L. "On some definitions of context-free languages", Programming and Computer Software. 1999, no. 5 pp.15-25.

Melnikov B., Melnikova A. "Pseudo-automata for Generalized Regular Expression", International Journal of Open Information Technologies, 2018, V. 6, no. 1, pp. 1-8.

Medvedev Y. "On the class of events accepting a representation in a finite automaton", Automata, M, Foreign Literature, 1956, pp. 385-401.

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. pp. 495-506.

Melnikov B. "Extended nondeterministic finite automata", Fundamenta Informaticae, 2010, V. 104, no. 3, pp. 255-256.

Melnikov B. "A new algorithm of the state-minimization for the nondeterministic finite automata", The Korean Journal of Computational and Applied Mathematics, 1999, no. 2, pp. 277-290.

Melnikov B., Sayfullina M. "On some algorithms of equivalent transformations of nondeterministic finite automata", Izvestiya of universities. Mathematics, 2009, no. 4, pp. 67-72 (in Russian),

(English translation: Mel'nikov B., Saifullina M. Some algorithms for equivalent transformations of nondeterministic finite automata. Russian Mathematics (Izv. VUZ), 2009, no. 4, pp. 54-56.)

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

Dolgov V., Melnikov B. "A Construction of Universal Final Automaton. I. From the Theory to the Practical Algorithms", Bulletin of Voronezh State University, Series: Physics. Mathematics, 2013, no. 2, pp. 173-181.

Jiang T., Ravikumar B. "Minimal NFA problems are hard", SIAM J.Comput. 1993, V. 22, no. 6, pp. 1117-1141.

Geldenhuys J., van der Merwe B., van Zijl L. "Reducing nondeterministic finite automata with SAT solvers", Springer. Finite-State Methods and Natural Language Processing. Lecture Notes in Computer Science, 2010, V. 6062, pp. 81-92.

Polak L., "Minimizations of NFA using the universal automaton",

International Journal of Foundations of Computer Science, 2005, V. 16, no. 5, pp. 999-1010.

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

Melnikov B., Melnikova A. "Edge-minimization of non-deterministic finite automata", The Korean J. of Comp. and Appl. Math., September 2001, V. 8, pp. 469-479 (Journal of Applied Mathematics and Computing).

Chomsky N., Schutzenberger M.-P. "The Algebraic Theory of Context-Free Languages", Computer Programming and Formal Systems, P. Braffort and D. Hirschberg (eds.), North Holland, 1963, pp. 118-161.


  • There are currently no refbacks.

Abava   FRUCT 2019

ISSN: 2307-8162