Tugurium/GTI

Glosario Terminología Informática

Chomsky hierarchy

0 jerarquía de Chomsky
Serie de cuatro clases de lenguajes formales definidos por Noam Chomsky en 1959, estableciendo con ellos las bases de la teoria de los lenguajes formales. Cada una de las clases es una subclase de la precedente.
- Clase 0, gramáticas sin restricciones. Está formada por todos los lenguajes recursivamente numerables, són gramáticas sin ninguna restricción. Pueden ser tratadas por la máquina de Turing.
- Clase 1, gramáticas sensibles al contexto. Está integrada por gramáticas sensitivas o sensibles al contexto. Pueden ser reconocidos por una máquina de Turing no determinista.
- Clase 2, gramáticas libres del contexto. La forman las gramáticas no dependientes del contexto o libres. Pueden ser reconocidos por un autómata con pila.
- Clase 3, gramáticas regulares. Formada por las gramáticas que generán lenguajes regulares, que pueden ser tratados por autómatas finitos.
1996-11-29