Reducing Operators for Generalized Grammars

Article type: Research Article

Authors: Novotný, Miroslav

Affiliations: Czechoslovak Academy of Sciences, Branch Brno, Czechoslovakia

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 G′ such that G and G′ generate the same language and G′ is in a certain sense smaller than or equal to G. The reducing operator ρ is used to characterize the so called harmonic languages.

Keywords: normed generalized grammar, permitting triple defined by means of derivatives, language grammatizable by means of derivatives, language weakly grammatizable by means of derivatives, harmonic grammar, harmonic language, reducing operator for generalized grammars

DOI: 10.3233/FI-1990-13302

Journal: Fundamenta Informaticae, vol. 13, no. 3, pp. 237-244, 1990