Construction of Contextual Grammars

Abstract

The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar G _n (V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative integer n _0 such that G _n =G _{n_0} (V,L) for any n ≥ n _0 .