Jerarquía de Chomsky
Clasificado en Informática
Escrito el en español con un tamaño de 10,25 KB
Jerarquía de Chomsky
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.
La jerarquía
La Jerarquía de Chomsky consta de cuatro niveles:
- Gramáticas de tipo 0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
- Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto.