>>16However, these scientists eventually found Chomsky’s theories unworkable for their computer systems. Other subsequent difficulties with the theories led to various debates between Chomsky and his critics that came to be known as the "Linguistics Wars", although they revolved largely around debating philosophical issues rather than linguistics proper.[84]
The Chomsky hierarchy, sometimes referred to as the Chomsky-Schützenberger hierarchy, is a containment hierarchy of classes of formal grammars. The hierarchy imposes a logical structure across different language classes and provides a basis for understanding the relationship between grammars (devices that enumerate the valid sentences within languages). In order of increasing expressive power it includes regular (or Type-3) grammars, context-free (or Type-2) grammars, context-sensitive (or Type-1) grammars, and recursively enumerable (or Type-0) grammars. Each class is a strict subset of the class above it, i.e., each successive class can generate a broader set of formal languages (infinite sets of strings composed from finite sets of symbols, or alphabets) than the one below.[194] In addition to being important in linguistics, the Chomsky hierarchy is also relevant in theoretical computer science, especially in programming language theory,[195] compiler construction, and automata theory.[196]