Jerarquia de chomsky

Solo disponible en BuenasTareas
  • Páginas : 2 (345 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de mayo de 2010
Leer documento completo
Vista previa del texto
Raúl Güitrón Gómez
Is193879
Jerarquía de Chomsky
{draw:frame} En 1959 Noam Chomsky clasifico las gramáticas en cuatro familias. Las gramáticas no restringidas, sensibles al contexto,independientes del contexto y las gramáticas regulares que se conocen como gramáticas de tipo cero, uno, dos y tres respectivamente. Los lenguajes que resultan de dichas gramáticas también se identifican conlenguajes de tipo cero, uno, dos y tres. A esta jerarquía de lenguaje se le conoce como la jerarquía de Chomsky.
Gramática Regular: Es aquella gramática cuyas reglas de reescritura tienen lassiguientes restricciones:
1.- El lado izquierdo de cualquier regla de reescritura debe consistir en un solo no terminal, el lado derecho debe ser un terminal seguido por un no terminal, o un soloterminal o la cadena vacía
En una gramática regular cualquier regla de la forma N {draw:frame} x podría remplazarse con el par de reglas siguientes:
Gramáticas independientes del contexto.
Adiferencia de las gramáticas regulares, estas gramáticas no tienen restricciones con respecto a la forma del lado derecho de sus reglas de reescritura aunque aun se requiere que el lado izquierdo de cadaregla sea un no terminal.
Siguiendo la regla rutinaria de aplicar siempre una regla de reescritura al no terminal mas a la izquierda en la cadena actual, a esto se le llama derivación por laizquierda.
S {draw:frame} zMNz {draw:frame} zaMaNz {draw:frame} zazaNz {draw:frame} zazabNbz {draw:frame} zazabzbz
Gramáticas no restringidas: Contiene reglas que transforman un número arbitrario desímbolos no vacío en otro número arbitrario, posiblemente vacío, de símbolos.
aAB -> a

bB -> aBC
Gramática sensible al contexto: Una gramática es tipo 1 monotónica si no contiene reglas dondeel lado izquierdo consista en más símbolos que el lado derecho:

|A| B

AF -> ABab
S -> aAB
Una gramática es tipo 1 sensible al contexto si todas sus reglas son sensibles al contexto. Una...
tracking img