Reducing Operators for Generalized Grammars

Abstract

Theory of reducing operators elaborated for pure generalized grammars in [5] is transferred to normed generalized grammars. There exists a reducing operator ρ such that. for any normed generalized grammar G the normed generalized grammars G, ρ(G) generate the same languages; furthemore: ρ(G) is a normed grammar if and only if there exists a normed grammar ${\mathit{G}}^{\prime }$ such that G and ${\mathit{G}}^{\prime }$ generate the same language and ${\mathit{G}}^{\prime }$ is in a certain sense smaller than or equal to G. The reducing operator ρ is used to characterize the so called harmonic languages.