GRAMMATICAL COMPLEXITY OF UNIMODAL MAPS WITH EVENTUALLY PERIODIC KNEADING SEQUENCES

We study complexity problems of the languages C(KS) generated from eve ntually periodic kneading sequences (abbreviated as KS) of unimodal ma ps on an interval. Two approaches have been used in this paper. The fi rst approach is to analyse the set of all distinct excluded blocks of L(KS). It is proved that this set is infinite and has a special semi-l inear structure. A method of calculating it is given and explained thr ough examples. The second approach is to find the finite automata acce pting L(KS). The minimal DFA accepting L(KS) is obtained. A formula is given to calculate the regular language complexities of L(KS). Finall y, we solve the problem of where all generalized composition rules, in cluding -composition rules, come from. Many new self-similar mappings from the set of all KS's into itself are obtained.