Chomsky hierarchy consists of several types of languages: regular, CFL, CSL, r.e.. What are the critera for a family of languages to qualify as a type of language in Chomsky hierarchy?
All the four types of language families in Chomsky hierarchy are (full) trios. is being a trios a necessary and/or sufficient condition for forming a type of languages in Chomsky hiearchy?
All the four types of language families in Chomsky hierarchy are (full) AFL's is being a AFL a necessary and/or sufficient condition for forming a type of languages in Chomsky hiearchy?
Thanks.
The Chomsky hierarchy is a particular division of context-free grammars into exactly four categories using three successively more restrictive conditions. By extension, these grammar categories define language categories (i.e. the set of languages for which there exists at least one grammar of Type I for values of I from 0 to 3). The properties of these four sets of languages, which are interesting, are a consequence of the three restrictions on the grammars which generate them, rather than being a motivation for the categorization.
It's not an extensible hierarchy, although Chomsky's 1958 paper On Certain Formal Properties of Grammars, which laid the foundation for the study of these grammatical types, ends with the suggestion that "it seems particularly important to try to arrive at some characterization of the languages of these various types26 and of the languages that belong to one type but not the next lower type in the classification," with a footnote adorning the word "types" starts "and several other types". (The paper is well worth reading if you are interested in the field.)
That is, Chomsky was not satisfied with this particularly hierarchy of restrictions on grammars, because it failed to provide a useful category of grammars which could be used to parse human languages, but nonetheless the particular hierarchy was worth studying.