Sub context-free L forms^†

^†Support of part of this work by the Austrian Federal Ministry for Science and Research is gratefully acknowledged

Abstract

Let F be an OL form or a so called clean EOL form. We show: if Fgenerates only CF languages then all languages generated by F are indeed linear. From the proof technique employed it further follows that for arbitrary OL forms F it is decidable whether or not F generates only CF languages.

Keywords:

• Form theory
• L systems
• L forms
• generative capacity
• linear languages
• context-free languages

C.R. Categories:

• 5.2

^†Support of part of this work by the Austrian Federal Ministry for Science and Research is gratefully acknowledged

^†Support of part of this work by the Austrian Federal Ministry for Science and Research is gratefully acknowledged

Notes

^†Support of part of this work by the Austrian Federal Ministry for Science and Research is gratefully acknowledged