On the Generative Capacity of Contextual Grammars with Catenation. Necessary Conditions

Article type: Research Article

Authors: Fortiş, Teodor Florin

Affiliations: University of the West, Faculty of Mathematics, b-dul V. Pârvan 4, 1900 Timişoara, Romania. E-mail: fortis@info.uvt.ro

Abstract: In this paper our attention is focused on the study of the properties for some families of contextual languages with catenation (see Fortiş, 1999, also Păun, 1982; Păun, 1997). Also, we are defining and analyzing some new properties characteristic to these families of languages. Using these properties we are able to establish some necessary conditions, and some pumping properties for families of contextual languages with catenation.

Keywords: Marcus contextual grammar, contextual grammar, contextual grammar with choice, contextual grammar with F-selection

DOI: 10.3233/INF-2001-12302

Journal: Informatica, vol. 12, no. 3, pp. 373-384, 2001