Jerarquías de gramáticas de chomsky

Jerarquías de Gramáticas de Chomsky

Chomsky clasificó las gramáticas en cuatro grandes grupos 0, 1, 2 y 3 de forma inclusiva.

Gramática tipo 0 Son las gramáticas más generales que sonrepresentadas por los lenguajes recursivamente enumerables. De forma u ::= v, donde u = xAy, x, y, v E (ΣT U ΣN)* y A E ΣN sin ninguna restricción. Se puede demostrar que todo lenguaje representado por unagramática de tipo 0 puede describirse también con una gramática de estructura de frases, si la parte derecha es más corta que la parte izquierda se dice entonces que se le aplica la regla compresora y laconvierte en una gramática compresora. Sea G= ({a, b}, {A, B, C}, A, P) donde P tiene las siguientes reglas de producción: A::= aABC |abC CB::=BC bB::=bb bC::=b Dado que bC::b es más larga de laparte izquierda, significa que el símbolo C terminal puede sustituirse por Ɛ cuando no está seguido de b. Es una gramática tipo 0, pero no de estructuras de frases, pues la regla CB::=BC no cumple lascondiciones requeridas. Se podría sustituir por cuatro reglas más añadiendo a la gramática símbolos no terminales adiciones X e Y, no habrá ninguno cambio serán iguales. CB::=XB XB::=XY XY::=BY BY::=BCGramática tipo 1 La regla de producción de estas gramáticas tiene la misma forma que las gramáticas de estructura de frases pero con una condición que ninguna regla de la gramática puede sercompresora. Es formada de la siguiente manera xAy ::= xvy donde x, y E (ΣT U ΣN)*, u
E (ΣT U ΣN)+ y A E ΣN. . Es decir dichas reglas indican que un solo símbolo no terminal A se transforma en la cadena v siestá flanqueado por la izquierda por la cadena x y por la derecha por la cadena y, además v no puede ser la cadena vacía. Sus lenguajes representados se les llaman dependientes del contexto olenguajes sensibles al contexto.

Su excepción es que una gramática del tipo 1 pueda contener la S ::= λ donde S es el axioma, de lo contrario el lenguaje no podría contener la palabra vacía. Esto...