Chomsky language hierarchy

Fig. 1. The four types of linear protein domain relationships. They have been ordered by degree of complexity in a manner analogous to the Chomsky finite automaton language hierarchy. Only the first three have been identified in nature thus far. This is no doubt that, in the fourth case, multiple simultaneous mutations would be required. If the linear order of the amino acid sequence is viewed as generated by a finite automaton, there is an equivalence with the Chomsky hierarchy. 

Most of grammatical inference research has been focused on learning regular and context-free languages. Although these are the basic classes of the Chomsky hierarchy, it has been proved that even to learn these classes is already too hard under certain learning paradigms. Next, we review the main formal models proposed in this field and some of the main learnability results obtained. 

Kornai, A. Natural languages and the Chomsky hierarchy. In Proceedings of EACL 85, pp. 1-7 (1985)... 

---