|
Description complexity of lindenmayer systemsKeywords: Context-free languages , L systems , Tree controlled gramma rs , Descriptional complexity , Nonterminal complexity Abstract: In this paper we study the nonterminal complexity of Lindenmayer systems withrespect to tree controlled grammars. We show that all 0L, D0Land E0L languages can begenerated by tree controlled grammars with at most five nonterminals. The results based onthe idea of using a tree controlled grammar in the t-normal form, which has the one activenonterminal, and a coding homomorphism
|