Constructions of Grammars by Means of Reducing Operators

Abstract

In [10] a reducing operator ρ was defined assigning a normed generalized grammar ρ(G) to any normed generalized grammar G in such a way that ρ(G) is in a certain sense less or equal to G and that both G and ρ(G) generate the same language. To any nontrivial language (V,L) a normed generalized grammar Gr(V,L) is assigned. Then ρ(Gr(V,L)) is proved to be a normed grammar if and only if (V,L) is a so called agreeable language.