Jerarquia de chomsky resumen
Páginas: 4 (830 palabras)
Publicado: 18 de noviembre de 2011
Noam Chomsky creó la teoría de las gramáticas generativas, la cual es considerada una de las más significativas contribuciones al campo de la linguística teórica hecha en el siglo XX.
Cuando NoamChomsky formalizó las gramáticas generativas en 1956, las clasificó en cuatro tipos que ahora se conocen como Jerarquía de Chomsky. Las diferencias entre los tipos de gramática es que tienen cada unareglas más restrictivas sobre las producciones y por lo que pueden generar menos lenguajes formales. Dos tipos importantes son las gramáticas independientes del contexto y las gramáticas regulares,que generan los lenguajes independientes del contexto y los lenguajes regulares respectivamente. Aunque menos poderosas que las gramáticas irrestrictas, que pueden expresar cualquier lenguaje acceptadopor una máquina de Turing, estos dos tipos de gramáticas restringidas se usan con más frecuencia ya que pueden implementarse analizadores eficientes para las mismas.
Gramática Irrestricta
En laJerarquia de Chomsky, una gramática irrestricta es una Gramatica a cuyas producciones no se le aplica ninguna restricción.
Las gramáticas irrestrictas pueden generar todos los lenguajes que puedenser aceptados por una máquina de Turing, por lo que juegan un papel importante en la teoría de computabilidad.
Gramática Sensible al Contexto
En una Gramatica sensible al contexto, cada produccióntiene la forma:
γΑβ→γωβ
donde:
Α ∈ N
γ, β ∈ (N ∪ T)*
ω ∈ (N ∪ T)+
Es decir, se permite el reemplazo del no-terminal Α en el lado izquierdo de la producción por la FormaSentencial ω sólo en el contexto γ_β. La gramática puede contener también la producción S?ε si el lenguaje que se requiere generar contiene la cadena vacía, pero solo si S no aparece en el ladoderecho de alguna producción.
Definición alternativa
Otra definición de gramática sensitiva al contexto es el de la clase de gramáticas con la restricción de que para toda regla:
α→β
se...
Cuando NoamChomsky formalizó las gramáticas generativas en 1956, las clasificó en cuatro tipos que ahora se conocen como Jerarquía de Chomsky. Las diferencias entre los tipos de gramática es que tienen cada unareglas más restrictivas sobre las producciones y por lo que pueden generar menos lenguajes formales. Dos tipos importantes son las gramáticas independientes del contexto y las gramáticas regulares,que generan los lenguajes independientes del contexto y los lenguajes regulares respectivamente. Aunque menos poderosas que las gramáticas irrestrictas, que pueden expresar cualquier lenguaje acceptadopor una máquina de Turing, estos dos tipos de gramáticas restringidas se usan con más frecuencia ya que pueden implementarse analizadores eficientes para las mismas.
Gramática Irrestricta
En laJerarquia de Chomsky, una gramática irrestricta es una Gramatica a cuyas producciones no se le aplica ninguna restricción.
Las gramáticas irrestrictas pueden generar todos los lenguajes que puedenser aceptados por una máquina de Turing, por lo que juegan un papel importante en la teoría de computabilidad.
Gramática Sensible al Contexto
En una Gramatica sensible al contexto, cada produccióntiene la forma:
γΑβ→γωβ
donde:
Α ∈ N
γ, β ∈ (N ∪ T)*
ω ∈ (N ∪ T)+
Es decir, se permite el reemplazo del no-terminal Α en el lado izquierdo de la producción por la FormaSentencial ω sólo en el contexto γ_β. La gramática puede contener también la producción S?ε si el lenguaje que se requiere generar contiene la cadena vacía, pero solo si S no aparece en el ladoderecho de alguna producción.
Definición alternativa
Otra definición de gramática sensitiva al contexto es el de la clase de gramáticas con la restricción de que para toda regla:
α→β
se...
Leer documento completo
Regístrate para leer el documento completo.