Construction of Contextual Grammars

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Novotný, Miroslav

Affiliations: Faculty of Informatics, Masaryk University, Botanická 68a, 602 00 Brno, Czech Republic. [email protected]

Note: [] Address for correspondence: Faculty of Informatics, Masaryk University, Botanická 68a, 602 00 Brno, Czech Republic

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.

Keywords: Contextual hypergrammar, contextual grammar, reducing operator

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 325-340, 2005