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
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 amb un símbol no terminal i , i cadenes de símbols terminals i no terminals. Les cadenes i poden ser buides, però no pot ser-ho. La regla està permesa si 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 amb un símbol no terminal i 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 també està permesa si 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.
| Tipus | Llenguatge | Autòmat | Normes de producció de la gramàtica |
|---|---|---|---|
| 0 | recursivament enumerable (LRE) | Màquina de Turing (MT) | Sense restriccions |
| 1 | depenent del context (LSC) | Autòmat linealment acotat | αAβ → αγβ |
| 2 | independent del context (LLC) | Autòmat a pila | A → γ |
| 3 | regular (RL) | Autòmat finit | A → aB A → a |