Simple EOL forms under uniform interpretation generating CF languages

Article type: Research Article

Authors: Albert, Jürgen^a | Maurer, Hermann^b | Rozenberg, Grzegorz^c

Affiliations: [a] University of Karlsruhe, Federal Republic of Germany | [b] Technische Universität Graz, Austria | [c] University of Leiden, The Netherlands

Abstract: In this paper we consider simple EOL forms (forms with a single terminal and single nonterminal) under uniform interpretations. We present a contribution to the analysis of generative power of simple EOL forms by establishing easily decidable necessary and sufficient conditions for simple EOL forms to generate (under uniform interpretations) CF languages only.

Keywords: context-free languages, Lindenmayer systems, grammatical similarity

DOI: 10.3233/FI-1980-3204

Journal: Fundamenta Informaticae, vol. 3, no. 2, pp. 141-156, 1980