On characterisation of language families in terms of inverse morphisms
Paavo Turakainen · International Journal of Computer Mathematics · 1984
Using a special substitution we present a general sufficient condition for a principal semiAFL L to contain a “hardest” language Lo such that each language in L is of the form for some morphism h. For instance, the families of context-free, multi-reset, quasi-realtime, context-sensitive, and recursively enumerable languages satisfy the condition. If a full principal semiAFL L fulfils it, then there exists Lo such that L consists of languages of the form where σ is an ε-free substitution of a special type. As an application we give a formula for a hardest recursively enumerable language. The problem of whether our condition is also necessary for the existence of Lo remains open. All principal semiAFLs are shown to possess weaker normal forms.