Jerarquia de Chomsky

Dins de les ciències de la computació, i en l'àrea dels llenguatges de programació, la jerarquia de Chomsky (també coneguda com a Jerarquia de Chomsky-Schützenberger) és una classificació jeràrquica de classes de gramàtiques formals que generen llenguatges formals.

Aquesta jerarquia de gramàtiques fou proposta per Noam Chomsky l'any 1956. També s'anomena en honor de Marcel-Paul Schützenberger, que va desenvolupar la teoria dels llenguatges formals.

La jerarquia de Chomsky consta de quatre nivells:

• Gramàtiques de tipus 0 (sense restriccions), que inclou a totes les gramàtiques formals. Aquestes gramàtiques generen tots els llenguatges que poden ser reconeguts per una màquina de Turing. Són els llenguatges coneguts com a llenguatges recursivament enumerables. Vegeu que aquesta categoria és diferent de la dels llenguatges recursius, que la decisió dels quals es pot fer per una màquina de Turing que s'aturi.
• Gramàtiques de tipus 1 (gramàtiques sensibles al context) generen els llenguatges sensibles al context. Aquestes gramàtiques tenen regles de la forma ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ amb ${\displaystyle A}$ un símbol no terminal i ${\displaystyle \alpha }$, ${\displaystyle \beta }$ i ${\displaystyle \gamma }$ cadenes de símbols terminals i no terminals. Les cadenes ${\displaystyle \alpha }$ i ${\displaystyle \beta }$ poden ser buides, però ${\displaystyle \gamma }$ no pot ser-ho. La regla ${\displaystyle S\rightarrow \epsilon }$ està permesa si ${\displaystyle S}$ no apareix a la part dreta de cap regla. Els llenguatges descrits per aquestes gramàtiques són exactament tots aquells llenguatges reconeguts per una màquina de Turing no determinista la cinta de la qual està acotada per un cert nombre enter de vegades la longitud d'entrada.
• Gramàtiques de tipus 2 (gramàtiques lliures del context) generen els llenguatges independents del context. Les regles són de la forma ${\displaystyle A\rightarrow \gamma }$ amb ${\displaystyle A}$ un símbol no terminal i ${\displaystyle \gamma }$ una cadena de símbols terminals i no terminals. Aquests llenguatges són aquells que es poden reconèixer per un autòmat a pila.
• Gramàtiques de tipus 3 (gramàtiques regulars) generen els llenguatges regulars. Aquestes gramàtiques es restringeixen a aquelles regles que tenen un símbol no terminal a la part esquerra, i a la part dreta un sol símbol terminal, possiblement seguit d'un símbol no terminal. La regla ${\displaystyle S\rightarrow \epsilon }$ també està permesa si ${\displaystyle S}$ no apareix a la part dreta de cap regla. Aquests llenguatges són aquells que es poden reconèixer amb un autòmat finit. Aquests llenguatges també es poden obtenir mitjançant expressions regulars.

Cal veure que el conjunt de gramàtiques corresponents als llenguatges recursius no forma part de la jerarquia.

La taula següent resumeix cadascuna de les 4 gramàtiques, la classe de llenguatge que genera, el tipus d'autòmat que el reconeix i la forma de les regles que ha de tenir.

• Chomsky, Noam «Three models for the description of language». IRE Transactions on Information Theory, 2, 1956, pàg. 113-124.
• Chomsky, Noam «On certain formal properties of grammars». Information and Control, 2, 1959, pàg. 137-167.
• Chomsky, Noam; Schützenberger, Marcel P.. «The algebraic theory of context free languages». A: Braffort, P.; Hirschberg, D.. Computer Programming and Formal Languages. Amsterdam: North Holland, 1963, p. 118-161.