Chomosky

left250002672715Clasificación de Chomsky de las gramáticas.
900007300Clasificación de Chomsky de las gramáticas.
righttop2015
Miguel Ángel Sánchez Medina
Sistemas 1
17/09/2015
400001000002015Miguel Ángel Sánchez Medina
Sistemas 1
17/09/2015

-184150693039000-727710216789000
Introducción
“En lingüística la jerarquía de Chomsky (ocasionalmente también llamada la jerarquía deChomsky–Schützenberger) es una clasificación jerárquica de distintos tipos de gramática formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
Chomsky clasificó lasgramáticas en cuatro grandes grupos 0, 1, 2 y 3 de forma inclusiva.
Tipo LenguajeAutómataNormas de producción de gramáticas0 recursivamente enumerable (LRE) Máquina de Turing (MT) Sin restricciones
1dependiente del contexto (LSC) Autómata linealmente acotadoαAβ → αγβ
2 independiente del contexto (LLC) Autómata con pilaA → γ
3 regular (LR) Autómata finitoA → aBA → a
DesarrolloGramática tipo 0Son las gramáticas más generales que son representadas 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 puededemostrar que todo lenguaje representado por una gramá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 diceentonces que se le aplica la regla compresora y la convierte 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::=BCbB::=bb bC::=b Dado que bC::b es más larga de la parte 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 estructurasde frases, pues la regla CB::=BC no cumple las condiciones 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...