Editing Chomsky hierarchy (section)

== History ==
The general idea of a hierarchy of grammars was first described by Noam Chomsky in "Three models for the description of language" during the formalization of [[transformational-generative grammar]] (TGG).{{sfn|Chomsky|1956}} [[Marcel-Paul Schützenberger]] also played a role in the development of the theory of [[formal language]]s; the paper "The algebraic theory of context free languages"{{Sfn|Chomsky|Schützenberger|1963}} describes the modern hierarchy, including context-free grammars.<ref name=Allott>{{cite book |last1=Allott |first1=Nicholas |last2=Lohndal |first2=Terje |last3=Rey |first3=Georges |chapter=Synoptic Introduction |title=A Companion to Chomsky |date=27 April 2021 |pages=1–17 |doi=10.1002/9781119598732.ch1 |isbn=9781119598701 |s2cid=241301126 |url=https://www.researchgate.net/publication/351812216}}</ref>

Independently, alongside linguists, mathematicians were developing models of computation (via [[automata]]). Parsing a sentence in a language is similar to computation, and the grammars described by Chomsky proved to both resemble and be equivalent in computational power to various machine models.<ref>{{cite book | last=Kozen | first=Dexter C. | title=Automata and computability | publisher=Springer | series=Undergraduate Texts in Computer Science | year=2007 | isbn=978-0-387-94907-9 | url=https://books.google.com/books?id=8lKyxS8_CNoC |pages=3–4}}</ref>