Jerarquía de Chomsky
Keywords: Jerarquía de Chomsky, 1956, Autómata, Autómata finito, Expresión regular, Gramática, Gramática formal, Gramática libre de contexto, Gramática regular
En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
| Tipo | Lenguaje | Autómata | Normas de producción de gramáticas |
|---|---|---|---|
| 0 | recursivamente enumerable (LRE) | Máquina de Turing (MT) | Sin restricciones |
| 1 | dependiente del contexto (LSC) | Autómata linealmente acotado | αAβ → αγβ |
| 2 | independiente del contexto (LLC) | Autómata a pila | A → γ |
| 3 | regular (RL) | Autómata finito | A → aB A → a |
| Tabla de contenidos |
Lenguajes Recursivamente Enumerables (de tipo 0)
Ver: Lenguaje recursivamente enumerable.
Las gramáticas que generan estos lenguajes pueden tener reglas compresoras.
Lenguajes Dependientes del Contexto (sensibles al contexto, de tipo 1)
No existen reglas compresoras, salvo, opcionalmente, la que deriva el axioma a la palabra vacía.
Existen reglas en las que un símbolo no terminal puede derivar a formas sentenciales distintas, según los símbolos que aparezcan a su alrededor
Lenguajes Independientes del Contexto (de contexto libre, de tipo 2)
La mayoría de los lenguajes de programación entran en ésta categoría.
Lenguajes Regulares (de tipo 3)
Se pueden expresar también mediante expresiones regulares.