Clasificación de Chomsky

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Tipos de gramáticas[editar]

Gramática de tipo 0 (sin restricciones)[editar]

Son todas las gramáticas que generan lenguajes capaces de ser reconocidos por una máquina de Turing. Estos lenguajes se los denomina lenguajes recursivamente enumerables e incluyen a todas las gramáticas formales.

Las producciones tienen la siguiente forma:

Gramáticas de tipo 1 (gramáticas sensibles al contexto)[editar]

Son todas las gramáticas que generan lenguajes capaces de ser reconocidos por una máquina de Turing no determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada.

Las producciones tienen la siguiente forma:

Gramáticas de tipo 2 (gramáticas libres del contexto)[editar]

Son todas las gramáticas que generan lenguajes capaces de ser reconocidos por un autómata con pila.

Las producciones tienen la siguiente forma:

Gramáticas de tipo 3 (gramáticas regulares)[editar]

Son todas las gramáticas que generan lenguajes capaces de ser reconocidos por un un autómata finito.

Las producciones tienen una de las siguientes formas:

Recursiva a derecha

Recursiva a izquiera

Relación entre los lenguajes[editar]

Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también dependiente del contexto, éste es recursivo y a su vez, recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en niveles anteriores.