Abstract

The classification of grammars that became known as the Chomsky hierarchy was an exploration of what kinds of regularities could arise from grammars that had various conditions imposed on their structure. Intersubstitutability is closely related to the way different levels on the Chomsky hierarchy correspond to different kinds of memory. This chapter deals with the general concept of a string‐rewriting grammar, which provides the setting in which the Chomsky hierarchy can be formulated. An unrestricted rewriting grammar works with a specified set of nonterminal symbols, and specified set of terminal symbols. From the very outset there were doubts about about whether context‐free grammars (CFGs) could form the basis of a theory of natural language syntax. The grammar's rewrite rules correspond to the automaton's transitions. Chomsky argued that even if the generative capacity of CFGs turned out to be sufficient for English, the resulting grammars would be unreasonably complex.