11.4 THE CHOMSKY HIERARCHY
We have now encountered a number of language families, among them the recursively enumerable languages (LRE), the context-sensitive languages (LCS), the context-free languages (LCF), and the regular languages (LREG). One way of exhibiting the relationship between these families is by the Chomsky hierarchy. Noam Chomsky, a founder of formal language theory, provided an initial classification into four language types, type 0 to type 3. This original terminology has persisted, and one finds frequent references to it, but the numeric types are actually different names for the language families we have studied. Type 0 languages are those generated by unrestricted grammars, that is, the recursively enumerable languages. ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
