Chomsky hierarchy
- 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.
- Chomsky, Avram NoamEstados Unidos, 1928 -
- context free grammargramática de contexto libre
- context sensitive grammargramática sensible al contexto
- context sensitive languagelenguaje sensible al contexto
- deep structureestructura profunda
- formal languagelenguaje formal
- regular grammargramática regular
- surface structureestructura superficial
- transformationtransformación
- Type-0 grammarsgramáticas de tipo 0
- Type-1 grammarsgramáticas de tipo 1
- Type-2 grammarsgramáticas de tipo 2
- Type-3 grammarsgramáticas de tipo 3