Context sensitive table lindenmayer languages and a relation to the lba problem : (prepublication)
Paul M. B. Vitanyi · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1975
Families of languages generated by classes of context sensitiveLindenmayer systems with tables using nonterminals are classified in the Chomsky hierarchy.It is shown that the family of languages generated by deterministic A-free left context sensitive L systems with two tables using nonterminals coincides with the context sensitive languages.Combined with the fact that the family of languages generated by deterministic A-free context sensitive L systems (with one table) using nonterminals is equal to the DLBA languages this shows the classic LBA problem to be equivalent to whether or not a trade-off is possible between one sided context with two tables and two sided context with one table for deterministic A-free L systems using nonterminals.Without the restriction to A-freeness such a trade-off is possible since the recursively enumerable languages are generated in both cases.By stating the £esults in their strongest form a complete classification of the considered language families is obtained since the hierarchies induced by the involved parameters (A-freeness, determinism, number of tables, amount of context, closure under various types of homomorphisms) basically collapse to the recursively enumerable languages, context sensitive languages and DLBA languages.