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

Abstract

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.