TIPOS DE GRAMÁTICA
Páginas: 6 (1412 palabras)
Publicado: 1 de junio de 2014
TIPOS DE GRAMÁTICA
El paradigma formal más famoso y rápidamente desarrollado para la caracterización de lenguajes, es el derivado del concepto de gramática generativa de Noam Chomsky. En Chomsky este celebérrimo lingüista norteamericano que intentó formalizar los lenguajes naturales, partiendo de que un lenguaje L es un subconjunto de todas las secuencias (finitas o no), que podemos formarmediante la concatenación de los elementos de un alfabeto Σ, define la gramática mediante la cuaterna siguiente:
Σ: Vocabulario finito de símbolos Terminales. Estos son los símbolos que realmente aparecen en una frase. Nunca aparecerán en el lado izquierdo de una producción (lo cual definiremos más adelante dentro de esta cuaterna). Los símbolos terminales deben ser símbolos validos del lenguaje.N: Conjunto finito de símbolos No Terminales, los cuales son metasímbolos que deben ser definidos por otras producciones (o reglas gramaticales), es decir, que también aparecen en el lado izquierdo de las mismas. Los símbolos No Terminales se pueden definir como variables sintácticas.
S: Un símbolo No Terminal básico (axiomático, según la definición de Chomsky). Sera el símbolo principal oaxioma que describirá oraciones enteras (y no subcadenas, como describen los símbolos No Terminales) de un lenguaje natural.
P: Conjunto, también finito, de reglas que nos dicen cómo se pueden generar las oraciones, como partiendo del axioma, podemos llegar a la oración terminal. Este conjunto será un simple subconjunto de:
Lo cual, expresado en una notación más clásica en lingüística seria:Donde:
Siendo posible que tanto α como β sean iguales a la cadena nula.
El lenguaje L así definido, se obtendría aplicando el siguiente procedimiento no algorítmico (no garantiza tiempo finito para una gramática genérica):
S es una formación oracional.
Si αβϒ es una forma oracional, y β = δ pertenece a P, αδϒ también será forma oracional.
Una forma oracional compuestaúnicamente por símbolos Terminales, constituirá una oración del lenguaje.
Jerarquía de Chomsky
A fin de precisar más qué tipo de gramática es capaz de generar un lenguaje lo más parecido posible a los naturales, Chomsky clasificó las gramáticas y lenguajes dentro de cuatro familias jerárquicamente ordenadas como modelos potenciales del lenguaje natural.
Esta clasificación, conocida comojerarquía de Chomsky, se establece aumentando las restricciones sobre la forma de las producciones. Así pues, tenemos:
Gramáticas no Restringidas (tipo 0)
Las gramáticas de tipo 0, son gramáticas sin restricciones, es decir, no hay restricciones ni para el lado izquierdo, ni para el lado derecho de las producciones.
Su potencia es la de una máquina de Turing, y sus reglas son del tipo:
α =β
No existe algoritmo que en tiempo finito nos diga si una cadena obedece o no las reglas de una gramática de reescritura tan generalizada.
Cuando Chomsky formuló sus objeciones a las gramáticas de estructura de sintagma (tipo 2), propuso la utilización de reglas de tipo 0 para el reordenamiento, elisión, etc., de elementos. La no existencia de algoritmo de parsing, mostraba que su potenciasuperaba en mucho a las lenguas naturales, y el formato de las reglas de reescritura se limitó mucho (los clásicos movimientos de sintagmas por tematización, interrogación).
Una gramática sin restricciones, es una cuaterna de la forma (V, Σ, P, S).
Donde:
V es un conjunto de variables o no terminales,
Σ (el alfabeto) es un conjunto finito de símbolos terminales,
P es un conjunto finito dereglas, y
S es un elemento de V llamado el símbolo inicial o axioma de la gramática.
Una producción de una gramática de este tipo, tiene la forma que ya hemos visto anteriormente (α = β), donde α ∈ (V ∪Σ)+ y donde β ∈ (V ∪Σ)*. Los conjuntos
V y Σ son disjuntos.
Gramática Tipo 1 o Dependientes del Contexto
Contiene reglas que se ajustan a:
β Aγ = βδγ
Este tipo de producciones,...
El paradigma formal más famoso y rápidamente desarrollado para la caracterización de lenguajes, es el derivado del concepto de gramática generativa de Noam Chomsky. En Chomsky este celebérrimo lingüista norteamericano que intentó formalizar los lenguajes naturales, partiendo de que un lenguaje L es un subconjunto de todas las secuencias (finitas o no), que podemos formarmediante la concatenación de los elementos de un alfabeto Σ, define la gramática mediante la cuaterna siguiente:
Σ: Vocabulario finito de símbolos Terminales. Estos son los símbolos que realmente aparecen en una frase. Nunca aparecerán en el lado izquierdo de una producción (lo cual definiremos más adelante dentro de esta cuaterna). Los símbolos terminales deben ser símbolos validos del lenguaje.N: Conjunto finito de símbolos No Terminales, los cuales son metasímbolos que deben ser definidos por otras producciones (o reglas gramaticales), es decir, que también aparecen en el lado izquierdo de las mismas. Los símbolos No Terminales se pueden definir como variables sintácticas.
S: Un símbolo No Terminal básico (axiomático, según la definición de Chomsky). Sera el símbolo principal oaxioma que describirá oraciones enteras (y no subcadenas, como describen los símbolos No Terminales) de un lenguaje natural.
P: Conjunto, también finito, de reglas que nos dicen cómo se pueden generar las oraciones, como partiendo del axioma, podemos llegar a la oración terminal. Este conjunto será un simple subconjunto de:
Lo cual, expresado en una notación más clásica en lingüística seria:Donde:
Siendo posible que tanto α como β sean iguales a la cadena nula.
El lenguaje L así definido, se obtendría aplicando el siguiente procedimiento no algorítmico (no garantiza tiempo finito para una gramática genérica):
S es una formación oracional.
Si αβϒ es una forma oracional, y β = δ pertenece a P, αδϒ también será forma oracional.
Una forma oracional compuestaúnicamente por símbolos Terminales, constituirá una oración del lenguaje.
Jerarquía de Chomsky
A fin de precisar más qué tipo de gramática es capaz de generar un lenguaje lo más parecido posible a los naturales, Chomsky clasificó las gramáticas y lenguajes dentro de cuatro familias jerárquicamente ordenadas como modelos potenciales del lenguaje natural.
Esta clasificación, conocida comojerarquía de Chomsky, se establece aumentando las restricciones sobre la forma de las producciones. Así pues, tenemos:
Gramáticas no Restringidas (tipo 0)
Las gramáticas de tipo 0, son gramáticas sin restricciones, es decir, no hay restricciones ni para el lado izquierdo, ni para el lado derecho de las producciones.
Su potencia es la de una máquina de Turing, y sus reglas son del tipo:
α =β
No existe algoritmo que en tiempo finito nos diga si una cadena obedece o no las reglas de una gramática de reescritura tan generalizada.
Cuando Chomsky formuló sus objeciones a las gramáticas de estructura de sintagma (tipo 2), propuso la utilización de reglas de tipo 0 para el reordenamiento, elisión, etc., de elementos. La no existencia de algoritmo de parsing, mostraba que su potenciasuperaba en mucho a las lenguas naturales, y el formato de las reglas de reescritura se limitó mucho (los clásicos movimientos de sintagmas por tematización, interrogación).
Una gramática sin restricciones, es una cuaterna de la forma (V, Σ, P, S).
Donde:
V es un conjunto de variables o no terminales,
Σ (el alfabeto) es un conjunto finito de símbolos terminales,
P es un conjunto finito dereglas, y
S es un elemento de V llamado el símbolo inicial o axioma de la gramática.
Una producción de una gramática de este tipo, tiene la forma que ya hemos visto anteriormente (α = β), donde α ∈ (V ∪Σ)+ y donde β ∈ (V ∪Σ)*. Los conjuntos
V y Σ son disjuntos.
Gramática Tipo 1 o Dependientes del Contexto
Contiene reglas que se ajustan a:
β Aγ = βδγ
Este tipo de producciones,...
Leer documento completo
Regístrate para leer el documento completo.