limpio






INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO
INGENIERÍA EN SISTEMAS COMPUTACIONALES


TEORIA COMPUTACIONAL


GRUPO:
2CV5


ALUMNO:
RAMÍREZ LLUVIAS JESÚSPROFESOR:
MOSCOSO MALAGON YOSAFAT

NOMBRE DEL TRABAJO:
JERARQUIA DE CHOMSKY




MEXICO, DF A 11 DE FEBRERO DE 2013





Jerarquía de Chomsky
La Jerarquía de Chomsky consta de cuatroniveles:
Gramáticas de tipo 0 (sin restricciones o recursivamente e numerables), (Maquina de Turing) que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces deser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerarles. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuyadecisión puede ser realizada por una máquina de Turing que se detenga. Las gramáticas que generan estos lenguajes pueden tener reglas compresoras.
Las reglas de producción son dela siguiente forma:

Ejemplo:
G1 = ({ 0, 1}, {A, B}, A, { A ::= B1 | 1, B ::= A0}) Gramática lineal por la izquierda que describe el lenguaje L1 = { 1, 101, 10101, ... } = {1(01) n| n = 0, 1, 2,...}
Gramáticas de tipo 1 (gramáticas sensibles/dependientes al contexto) (maquina no determinista Linear-limitada de Turing) generan los lenguajes sensibles al contexto. Estas gramáticas tienenreglas de la forma  con  un no terminal y ,  y  cadenas de terminales y no terminales. Las cadenas  y  pueden ser vacías, pero  no puede serlo. La regla  está permitida si no aparece en la parte derechade ninguna regla. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por uncierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados. No existen reglas compresoras, salvo, opcionalmente, la que deriva el axioma a la...