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

Abstract

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.