Constructions of Grammars by Means of Reducing Operators

Article type: Research Article

Authors: Novotný, Miroslav

Affiliations: Czechoslovak Academy of Sciences, Branch Brno

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.

Keywords: normed generalized grammar, normed grammar, reducing operator, permitting triple with derivatives, canonical permitting triple with derivatives, agreeable language

DOI: 10.3233/FI-1989-12306

Journal: Fundamenta Informaticae, vol. 12, no. 3, pp. 401-411, 1989