INTRODUCCION
El
siguiente trabajo hablara acerca de lo relacionado con Chomsky dentro su
gramática generativa que pretende ser
capaz de generar una infinita cantidad de construcciones sintácticas a partir
de un número limitado de reglas y unidades abstractas, una propiedad conocida como recursividad; así mismo se
tratara de su forma normal que no es más que una forma de expresar ciertos
lenguajes.
Las ideas básicas de los modelos incluidos en esta corriente tienen su
origen en la teoría
estándar formulada por Noam Chomsky. El núcleo
común de todos los modelos generativos sería el intentar diseñar un dispositivo
formal que permita describir, analizar y especificar las oraciones de una
lengua natural en forma simple, exhaustiva y general.
También se tratara acerca de los autómatas con transición de cerradura y
los autómatas de pila que es un autómata finito no determinista
asociado a una pila que puede utilizar para almacenar una cadena de longitud
arbitraria. La pila se puede leer y modificar sólo por su parte superior.
1]
1]
GRAMATICA
GENERATIVA DE CHOMSKY
La gramática generativa se refiere a un conjunto
de marcos teóricos para el estudio de la sintaxis de las lenguas. Una
gramática generativa proporciona un conjunto de reglas o principios que
predicen correctamente las combinaciones que aparecen en oraciones gramaticalmente
correctas para una determinada lengua.
Por tanto, la tarea del lingüista
consistirá en hallar el sistema práctico que implique la competencia y que será expresado
en forma de reglas cuyo conjunto constituye la gramática.
Así, podemos decir que la
gramática generativa es el conjunto de reglas que permiten generar todas y cada
una de las manifestaciones lingüísticas de una lengua. Pero para elaborar esa teoría
lingüística se podría: Descubrir la gramática de una lengua sobre la base de un
corpus representativo y garante. Chomsky piensa que esto es imposible.
Decidir
si una gramática ya existente es adecuada o no lo es. Sin premisas de criterio,
sería un apriorismo inadmisible.
Valorar unas cuantas gramáticas e
intentar aproximarse a la descripción más perfecta.
Hay que anotar que la solución
última implica a la segunda, por lo que se viene a caer en el condenado
apriorismo.
Chomsky lleva razón al decir que
una teoría debe ser independiente del material concreto que se va a describir
con ella. Pero una teoría exige un número de premisas implícitas que se reducen
al mínimo, y las definiciones sucesivas deben ir siempre apoyadas en lo ya
expuesto. En la práctica equivale esto a la necesidad de introducir las
definiciones previas antes de las que las presuponen; es decir, partir de lo
más sencillo para llegar a lo más complejo como lo exigen la segunda y tercera
reglas cartesianas.
TEORÍA GRAMÁTICA DESCRIPCIÓN
Sin embargo, Chomsky toma la
teoría de las gramáticas más logradas, no se detiene a definir los conceptos
teóricos básicos que luego va a emplear, como “verbo”, “sustantivo”… Y, sobre
esa teoría, deducida de otras gramáticas no elaboradas científicamente,
organiza su gramática de reglas generativas.
La pregunta es la siguiente: ¿si
no resulta esa teoría por fallo científico de los fundamentos en que se apoya
no probados lógicamente?
La respuesta de Chomsky es
sencilla: ¡Se cambia! Es lo que ha hecho en su segunda época. La teoría
gramatical está sujeta a revisiones continuas. Y esto es necesario precisamente
por el dinamismo cambiante de la realidad de la lengua.
Hay otra pregunta: ¿si resulta
exacta esa teoría tras ciertos perfeccionamientos? Es lo que constituye la base
de toda invención, de todo descubrimiento basado en el “dominio del azar”, algo
cautivador y atrayente en sumo grado. No nos extraña que la lingüística
transformacional haya sido calificada de “maravillosa aventura”.
La gramática generativa asume
como otros modelos teóricos, que una secuencia de discurso puede descomponerse
en constituyentes
sintácticos. Un constituyente sintáctico es una combinación de
palabras que posee un núcleo
sintáctico del que el constituyente hereda sus propiedades combinatorias. No
cualquier conjunto de palabras es un constituyente, por ejemplo una preposición
requiere estar unida
una un sintagma nominal o
un sintagma
determinante para formar un constituyente. Los constituyentes.Sintácticos forman un conjunto
parcialmente ordenado, a través de la relación 
usualmente representada
como y que se interpreta como
"el constituyente X es parte del constituyente Y".
usualmente representada
como y que se interpreta como
"el constituyente X es parte del constituyente Y".
La peculiaridad de la
gramática generativa más reciente es que las secuencias del habla tal como aparecen
pueden presentar constituyentes sintácticos desplazados, es decir, las forma
aparente de una oración es el resultado tanto de ensamblaje de constituyentes,
como de alteración del orden de estos, según los principios del movimiento
sintáctico (en realidad no es un intercambio de orden lineal sino el cambio
de posición de uno de los dos constituyentes hacia una posición vacía que puede
anteceder la posición lineal del otro constituyente). Además la gramática
generativa impone restricciones sobre los rasgos gramaticales de
ciertos elementos sintácticos, dando lugar a relaciones de concordancia
gramatical o rección gramatical.
FORMA NORMAL DE CHOMSKY
La
normativa lingüística se basa en una serie de usos expresivos que deben
acatarse para hablar y escribir correctamente un idioma. Para la determinación
del concepto «correcto» se toman en cuenta los criterios de uso siguientes:
·
Conformación de
un sistema lingüístico a partir de su componente etimológico y de su evolución
histórica.
·
Frecuencia en la
lengua literaria.
En
ocasiones lo normativo admite diferencias según distintas variedades
lingüísticas. Ejemplos dentro del territorio de dominio del español
Completamos el
estudio sobre las simplificaciones gramaticales demostrando que todo LIC no
vacío sin å tiene
una gramática G en la que todas las producciones tienen una de las dos
formas siguientes:
1. A→BC, donde A,
B y C son variables, o
2. A→a, donde A es
una variable y a es un símbolo terminal.
Además, G no
contiene símbolos inútiles. Una gramática así se dice que está en la forma
normal de Chomsky,
o FNC.
Para expresar
una gramática en la forma normal de Chomsky, partimos de una que satisfaga las
restricciones
del siguiente
Teorema: La
gramática no contiene producciones-å , ni
producciones unitarias ni símbolos
N. Chomsky es el primer lingüista
que propuso las gramáticas independientes del contexto como una forma de
describir los lenguajes naturales, y que demostró que toda GIC podía expresarse
de esta forma. Es interesante observar que la FNC no parece tener usos
importantes en la lingüística natural, aunque
veremos que sí tiene otras aplicaciones, como por ejemplo comprobar de manera
eficiente la pertenencia de una cadena a un lenguaje independiente del contexto
inútiles. Toda producción de dicha gramática es de la forma A→a, que es una forma permitida por
la FNC, o tiene un cuerpo de longitud 2 o superior. Nuestras tareas son
entonces:
a) Conseguir que todos los
cuerpos de longitud 2 o superior estén formados sólo por variables.
b) Descomponer los cuerpos de
longitud 3 o superior en una cascada de producciones, teniendo cada una de ellas
un cuerpo formado sólo por dos variables.
La construcción para (a) es la
siguiente: para todo símbolo a que aparezca en un cuerpo de longitud 2 o
superior, creamos una nueva variable, por ejemplo A. Esta variable sólo
tiene una producción, A →a. Ahora empleamos A en
lugar de a en cualquier lugar que aparezca esta última dentro de un
cuerpo de longitud 2 o superior. En este punto, toda producción tendrá un
cuerpo formado por un sólo símbolo terminal o por al menos
dos variables y
ningún símbolo terminal.
Para el paso
(b), tenemos que descomponer dichas producciones A→B1B2 · · ·Bk, para k ≥ 3, en un grupo
de producciones
con dos variables en cada cuerpo. Introducimos k−2 nuevas
variables, C1,C2, . . .
,Ck−2. La
producción
original se reemplaza por las k−1 producciones:
A→B1C1, C1 →B2C2, . . .
,Ck−3 →Bk−2Ck−2, Ck−2 →Bk−1Bk
TEOREMA :
Si G es
una GIC cuyo lenguaje consta de al menos una cadena distinta de å , entonces
existe una gramática G1
en la forma
normal de Chomsky, tal que L(G1) = L(G)−{å }.
AUTOMATA CON TRANCISION DE CERRADURA
Un autómata
con €-transiciones es un AFN
donde
la función de transición está definida así:
La €-transición
permite al autómata cambiar internamente de estado sin consumir el símbolo leído
sobre la cinta.
EQUIVALENCIA ENTRE LOS AFN€_ Y AFN
Los AFN-€son
computacionalmente equivalentes al modelo AFN.
Teorema:
EISC Autómatas
Dado un AFN-€ se puede construir un AFN M0 equivalente
a M´ es decir L(M) = L(M´)
Definición: Para
todo estado q 2 Q, definimos la cerradura de q como:
€ − c (q) = {p |
p es accesible desde q sin consumir nada en la entrada}
€− c {q1, q2, .
. . , qk} = _ − c(q1) [ . . . [ _ − c(qk)
A partir de un M
= (Q,_ [ {_}, q0, T,4) que tiene _-transiciones, se puede construir un AFN
Construir un
AFN-€ que reconozca sobre € = {a, b, c}, el lenguaje L = a*b*c*
AUTOMATA DE PILA
Existe un tipo de autómata que
define los lenguajes independientes del contexto. Dicho autómata, conocido como
“autómata a pila”, es una extensión del autómata finito no determinista con
transiciones-å
, el cual constituye
una forma de definir los lenguajes regulares. El autómata a pila es
fundamentalmente un AFN-å con la
adición de una pila. La pila se puede leer, se pueden introducir elementos en
ella y extraer sólo el elemento que está en la parte superior de la misma,
exactamente igual que la estructura de datos de una “pila”.
El autómata a pila es un autómata
finito no determinista con transiciones-å y
una capacidad adicional: una pila en la que se puede almacenar una cadena de
“símbolos de pila”. La presencia de una pila
significa que, a diferencia del
autómata finito, el autómata a pila puede “recordar” una cantidad infinita de
información. Sin embargo, a diferencia de las computadoras de propósito
general, que también tienen la capacidad de recordar una cantidad
arbitrariamente grande de información, el autómata a pila sólo puede acceder a
la información disponible en su pila de acuerdo con la forma de manipular una
pila
En una
transición, el autómata a pila:
1. Consume de la
entrada el símbolo que usa en la transición. Si como entrada se utiliza å , entonces no se
consume ningún símbolo de entrada.
2. Pasa a un
nuevo estado, que puede o no ser el mismo que el estado anterior.
3. Reemplaza el
símbolo de la parte superior de la pila por cualquier cadena. La cadena puede
ser å,
lo que corresponde a una extracción de la pila. Podría ser el mismo símbolo que
estaba anteriormente en la cima de la pila; es decir, no se realiza ningún
cambio en la pila. También podría reemplazar el símbolo de la cima de la pila
por otro símbolo, lo que cambiaría la cima de la pila pero no añade ni extrae
ningún símbolo. Por último, el símbolo de la cima de la pila podría ser
reemplazado por dos o más símbolos, lo que (posiblemente) tendría el efecto de
cambiar el símbolo de la cima de la pila, añadiendo después uno o más nuevos
símbolos a la pila.
Un Autómata a Pila se define como la
séptupla:(Σ, P, Q, A0, q0, f, F)
Donde:
Σ: alfabeto de
entrada.
P: alfabeto de
la pila.
Q: conjunto de
estados.
A0: símbolo
inicial de la pila (#).
q0: símbolo
inicial del conjunto de estados.
f: función de
transición. Es una aplicación de
QxΣ{λ}xP en el
conjunto de partes de P(QxP)*.
F: conjunto de estados finales o de
aceptación.
Función de transición. Interpretamos la función f de la siguiente
forma:
f(q, a, A) =
{(q1,Z1),..., (qn,Zn)}: Si el AP se encuentra en el estado q, lee el
símbolo a de la cinta de entrada, y aparece el símbolo A en el
tope de la pila, pasará al estado qi (ni1), borrará el símbolo A de
la pila e introducirá la palabra Zi, situando la cabecera de la misma en
el tope de la pila, y avanzando una posición en la cinta de entrada.
f(q, λ, A) = {(q1,Z1),..., (qn,Zn)}: Si
el AP se encuentra en el estado q y aparece el símbolo A en el
tope de la pila, pasará al estado qi (ni1), borrará el símbolo A de
la pila e introducirá la palabra Zi, situando la cabecera de la misma en
el tope de la pila, y mantendrá la misma posición en la cinta de entrada.
AUTOMATA DE PILA DETERMINISTA
Dado un AP, podemos describir el proceso
de aceptación o rechazo de una palabra de Σ* mediante una serie de
descripciones instantáneas de la forma (q,
x, Z)que definen respectivamente el estado del AP, la entrada que queda
por leer, y el contenido de la pila en un momento dado.
Decimos que una
descripción instantánea (q, az, AZ) precede a otra (p, z, YZ) en un paso y
se expresa como:(q, az, AZ)(p, z, YZ), si (p, Y)f(q, a, A).
Decimos que una
descripción instantánea (q, az, AZ)precede a otra (p, z, YZ) en n pasos y
se expresa como:(q, az, AZ) * (p, z, YZ), si existen una serie de
descripciones que cumplen la relación de precedencia anterior de una en una.
CONVENIOS EN LA NOTACIÓN DE LOS
AUTÓMATAS A PILA
Continuaremos empleando los
convenios respecto del uso de símbolos que hemos presentado para los
autómatas finitos y las
gramáticas. Al trasladar la notación, resulta útil darse cuenta de que los
símbolos
de la pila desempeñan un papel
análogo a la unión de los símbolos terminales y las variables en una GIC.
Así:
1. Los símbolos del alfabeto de
entrada se representan mediante las letras minúsculas próximas al
principio del alfabeto, por
ejemplo, a, b.
2. Los estados se representan
mediante q y p, típicamente, u otras letras próximas en orden
alfabético.
3. Las cadenas de símbolos de
entrada se representan mediante las letras minúsculas próximas al final
del alfabeto, por ejemplo, w o
z.
4. Los símbolos de la pila se
representanmediante las letras mayúsculas próximas al final del alfabeto,
por ejemplo, X o Y.
5. Las cadenas
de los símbolos de pila se representarán mediante letras griegas, por ejemplo,
α o γ .
BIBLIOGRAFIA
·
Teoría de
autómatas y lenguajes formales.
·
Introducción a
la teoría de autómatas, lenguajes y computación
John E.
Hopcroft; Jeffrey D. Ullman Editorial Cecsa
No hay comentarios:
Publicar un comentario