Cargando...
Lengua
Expresando la anterior definición de una manera más general, afirmamos que una Lengua L cualquiera es un conjunto de cadenas finitas de símbolos que pertenecen a un conjunto finito. Este último conjunto es denominado Alfabeto de L. Es decir, una Lengua L es un conjunto de variaciones con repetición sobre elementos de un alfabeto. Debe notarse que esta definición no se limita a las denominadas lenguas naturales. Por lengua natural entendemos uno de los miles de sistemas verbales, orales, que los seres humanos usan y han usado para comunicarse entre sí y que no han surgido en virtud de actos conscientes de creación. En efecto, de acuerdo a este modelo, el conjunto de oraciones de uno cualquiera de los sistemas formalizados de la matemática puede considerarse como Lengua. Con respecto a las lenguas naturales, ya sea en su forma hablada o escrita, todas ellas son Lenguas en el sentido anteriormente presentado, ya que cada una de ellas se caracteriza por la posesión de un número finito de fonemas (lengua hablada) o de letras (lengua escrita), siendo cada oración representable como una secuencia finita con repetición de estos elementos.
Para Chomsky, la sintaxis trata de estudiar los principios y procesos mediante los cuales se construyen las oraciones de las lenguas particulares. La investigación sintáctica de una lengua determinada tiene como objetivo la construcción de una Gramática. Esta Gramática puede ser considerada como una especie de ingenio o dispositivo (device) generador de las oraciones de la lengua que se trata de analizar.
Gramática
El análisis lingüístico de una Lengua L tiene como propósito fundamental establecer una delimitación entre las cadenas gramaticales que son oraciones de L y las agramaticales que no son oraciones de L, y estudiar seguidamente la estructura de las secuencias gramaticales. Por cadenas gramaticales entendemos aquellas que son aceptables para un hablante nativo. El objetivo es construir una Gramática capaz de llevar a cabo la tarea de generar estas oraciones de un modo efectivo. Una Gramática lograda (successful) es entonces -para Chomsky- un ingenio que genere todas las secuencias gramaticales de L y ninguna de las agramaticales.
Por tanto, podemos decir que una Gramática de L es un sistema de reglas que especifica el conjunto de oraciones de L y asigna a cada oración una descripción estructural. La descripción estructural de una oración da cuenta de sus elementos constitutivos y su organización.
Autómata de estados finitos
y gramática correspondiente
Consideramos un dispositivo mecánico simple que pueda estar en un número finito de estados internos y ejecutar dos operaciones simultáneas: 1) Pasar a un nuevo estado interno y, 2) Imprimir uno de un conjunto finito de símbolos en una cinta. Desde ese nuevo estado puede pasar -del mismo modo anterior- a otro e imprimir un nuevo símbolo contiguo al primero ya impreso.
Nunca puede trasladarse hacia atrás en una cinta ni sustituir un símbolo ya impreso por uno nuevo. Un conjunto particular de estados recibe el nombre de estados iniciales y otro conjunto el de estados finales. Cada secuencia de símbolos que resulta de comenzar en un estado inicial, pasar sucesivamente de estado a estado imprimiendo a cada paso el símbolo correspondiente de acuerdo a lo establecido por un conjunto finito de instrucciones y acabar en un estado final, es llamada una Oración generada por la máquina. El conjunto de oraciones generadas por la máquina es un lenguaje perfectamente definido y en concordancia con las consideraciones que efectuáramos al inicio. Las “máquinas” de este tipo (en realidad son dispositivos lógicos sin existencia física) conforman un tipo perfectamente estudiado de máquinas abstractas o autómatas, llamadas Autómatas de Estados Finitos. En términos sencillos, es posible interpretar cada operación del autómata como una regla de una Gramática. Esta Gramática -generada por un autómata de estados finitos- es denominada Gramática de Estados Finitos. Y si estamos de acuerdo en que una Gramática de L es un conjunto de reglas que genera las oraciones de L, siendo L a su vez el conjunto de dichas oraciones, definimos a la Lengua L generada por una gramática de estados finitos como una Lengua Regular o Lengua de Estados Finitos.
Analicemos una lengua cuyo alfabeto esté compuesto únicamente por dos letras “a” y “b” cuyas oraciones son: “ab, aabb, aaabbb...” y en general todas las oraciones que constan de “n” casos de “a” seguidos de “n” casos de “b”. Notemos que en realidad estas oraciones se generan por la autoincrustación de la oración “ab” en cualquier oración precedente. Una Gramática que genera una Lengua cuyas oraciones son autoincrustantes se denomina Gramática Autoincrustante. Supongamos la existencia de una Lengua dada L1 que puede ser generada simultáneamente por varias gramáticas. Si todas estas gramáticas son autoincrustantes, la Lengua L1 se denomina Esencialmente Autoincrustante.
En cambio, una Lengua L2 que pueda ser generada tanto por una gramática autoincrustante como por una no-autoincrustante se denomina No Esencialmente Autoincrustante. Al respecto, la afirmación siguiente -que es un Teorema de la Lengua- es válida: “Un lenguaje es regular si y sólo si no es esencialmente autoincrustante”. Ello significa que la lengua generada por una gramática de estados finitos necesariamente es no autoincrustante. Si podemos demostrar que una lengua dada es esencialmente autoincrustante, habremos demostrado que no es regular. Vemos así que el inglés -Chomsky utiliza exclusivamente el inglés en sus ejemplos- y cualquier otra lengua natural tiene construcciones para cuya descripción hay que hacer uso de elementos autoincrustantes. De ahí concluye Chomsky que el inglés no es una lengua regular, lo que significa que una gramática basada en un autómata de estados finitos no puede generar todas sus oraciones adecuadamente. Esto puede tomarse como válido también para otras lenguas naturales.
Máquina Universal de Turing
Este dispositivo es denominado así debido a que su creador fue el matemático británico Alan Turing. Supongamos un dispositivo irreflexivo y absolutamente obediente, capaz de realizar cualquier tarea que le fuera encomendada. Se indica a este ingenio, dado un conjunto finito de números, encontrar cuál es el mayor de ellos, de acuerdo a las siguientes instrucciones: 1) Lea el primer número N1 del conjunto y anótelo en un dispositivo de almacenamiento (memoria), 2) Lea el siguiente número N2, 3) Compárelo con el existente en la memoria, 4) Si N2N1 entonces borre de la memoria el número existente y remplácelo por N2, leyendo posteriormente el número que sigue, 6) Repita el mismo procedimiento y al llegar al último número deténgase. Vemos que al finalizar este proceso, el último número que el autómata registró en la memoria será efectivamente el mayor de la serie.
Es decir, para cierto tipo de problemas que admiten solución, pueden definirse procedimientos que encontrarán dicha solución en un número finito de pasos. Dichos procedimientos son denominados Procedimientos Algorítmicos. A grandes rasgos, un algoritmo es un procedimiento mediante el cual podemos obtener la solución de un problema partiendo de unos datos, mediando un número finito y determinado de operaciones. De acuerdo a la concepción chomskyana de gramática, la misma no es otra cosa que un dispositivo generador de frases. Por tanto podemos decir que una gramática es un algoritmo generador de frases. El matemático Alonso Church formuló la aserción conocida como Tesis de Church, que expresa lo siguiente: “Si un proceso puede especificarse en una serie de etapas mecánicas y completamente explícitas, puede ser realizado por una Máquina Universal de Turing”. Y como las operaciones de cualquier gramática pueden ser objeto de formulaciones precisas, las mismas pueden ser generadas por una Máquina Turing. Es decir -así como el Autómata de Estados Finitos- la Máquina de Turing puede generar una gramática, y ésta a su vez, las oraciones correspondientes a la lengua L definida por ella.
Capacidad generativa de las gramáticas
Se define la capacidad generativa de una gramática como el conjunto de lenguajes factibles de ser generados por ésta. Dadas dos gramáticas G1 y G2, diremos que la capacidad generativa de G1 es mayor que la de G2 si cada lenguaje generado por G2 también puede ser generado por G1 pero no viceversa.
JerarquIa de las gramáticas. Conclusión
Una Máquina Turing puede producir una gramática capaz de generar una lengua regular pero un Autómata de Estados Finitos no tiene la capacidad generativa para producir las gramáticas factibles de ser generadas por un dispositivo Turing. Es decir, entre las gramáticas -y consecuentemente entre los autómatas- existe una jerarquía definida por la capacidad generativa. Esta jerarquía entre los autómatas, las gramáticas y las correspondientes lenguas generadas ubica a las gramáticas denominadas G0, producidas por los autómatas Turing y sus lenguas correspondientes (Lenguajes Enumerables Recursivamente) en la escala superior de capacidad generativa.
En la misma clasificación, las denominadas gramáticas G4, originadas por los autómatas de Estados Finitos (que generan las Lenguas Regulares) ocupan el último lugar.
Sólo nos queda por ubicar en la jerarquía anteriormente mencionada a las gramáticas que originan las llamadas lenguas naturales. El examen hecho de los autómatas de estados finitos y de las gramáticas de estados finitos ha probado que las lenguas naturales sobrepasan la esfera de las gramáticas del tipo G4. Otros autores afirman que las lenguas naturales deben ser consideradas -como máximo- sistemas enumerables recursivamente, lo que es decir, generadas por gramáticas G0 que tienen su origen en autómatas Turing. Ello nos lleva a concluir lo siguiente: la gramática de una lengua natural es menos general que una gramática G0 generada por una Máquina Universal de Turing pero más potente que una gramática G4 generada por un Autómata de Estados Finitos.
Enio Quevedo
Expresando la anterior definición de una manera más general, afirmamos que una Lengua L cualquiera es un conjunto de cadenas finitas de símbolos que pertenecen a un conjunto finito. Este último conjunto es denominado Alfabeto de L. Es decir, una Lengua L es un conjunto de variaciones con repetición sobre elementos de un alfabeto. Debe notarse que esta definición no se limita a las denominadas lenguas naturales. Por lengua natural entendemos uno de los miles de sistemas verbales, orales, que los seres humanos usan y han usado para comunicarse entre sí y que no han surgido en virtud de actos conscientes de creación. En efecto, de acuerdo a este modelo, el conjunto de oraciones de uno cualquiera de los sistemas formalizados de la matemática puede considerarse como Lengua. Con respecto a las lenguas naturales, ya sea en su forma hablada o escrita, todas ellas son Lenguas en el sentido anteriormente presentado, ya que cada una de ellas se caracteriza por la posesión de un número finito de fonemas (lengua hablada) o de letras (lengua escrita), siendo cada oración representable como una secuencia finita con repetición de estos elementos.
Para Chomsky, la sintaxis trata de estudiar los principios y procesos mediante los cuales se construyen las oraciones de las lenguas particulares. La investigación sintáctica de una lengua determinada tiene como objetivo la construcción de una Gramática. Esta Gramática puede ser considerada como una especie de ingenio o dispositivo (device) generador de las oraciones de la lengua que se trata de analizar.
Gramática
El análisis lingüístico de una Lengua L tiene como propósito fundamental establecer una delimitación entre las cadenas gramaticales que son oraciones de L y las agramaticales que no son oraciones de L, y estudiar seguidamente la estructura de las secuencias gramaticales. Por cadenas gramaticales entendemos aquellas que son aceptables para un hablante nativo. El objetivo es construir una Gramática capaz de llevar a cabo la tarea de generar estas oraciones de un modo efectivo. Una Gramática lograda (successful) es entonces -para Chomsky- un ingenio que genere todas las secuencias gramaticales de L y ninguna de las agramaticales.
Por tanto, podemos decir que una Gramática de L es un sistema de reglas que especifica el conjunto de oraciones de L y asigna a cada oración una descripción estructural. La descripción estructural de una oración da cuenta de sus elementos constitutivos y su organización.
Autómata de estados finitos
y gramática correspondiente
Consideramos un dispositivo mecánico simple que pueda estar en un número finito de estados internos y ejecutar dos operaciones simultáneas: 1) Pasar a un nuevo estado interno y, 2) Imprimir uno de un conjunto finito de símbolos en una cinta. Desde ese nuevo estado puede pasar -del mismo modo anterior- a otro e imprimir un nuevo símbolo contiguo al primero ya impreso.
Nunca puede trasladarse hacia atrás en una cinta ni sustituir un símbolo ya impreso por uno nuevo. Un conjunto particular de estados recibe el nombre de estados iniciales y otro conjunto el de estados finales. Cada secuencia de símbolos que resulta de comenzar en un estado inicial, pasar sucesivamente de estado a estado imprimiendo a cada paso el símbolo correspondiente de acuerdo a lo establecido por un conjunto finito de instrucciones y acabar en un estado final, es llamada una Oración generada por la máquina. El conjunto de oraciones generadas por la máquina es un lenguaje perfectamente definido y en concordancia con las consideraciones que efectuáramos al inicio. Las “máquinas” de este tipo (en realidad son dispositivos lógicos sin existencia física) conforman un tipo perfectamente estudiado de máquinas abstractas o autómatas, llamadas Autómatas de Estados Finitos. En términos sencillos, es posible interpretar cada operación del autómata como una regla de una Gramática. Esta Gramática -generada por un autómata de estados finitos- es denominada Gramática de Estados Finitos. Y si estamos de acuerdo en que una Gramática de L es un conjunto de reglas que genera las oraciones de L, siendo L a su vez el conjunto de dichas oraciones, definimos a la Lengua L generada por una gramática de estados finitos como una Lengua Regular o Lengua de Estados Finitos.
Analicemos una lengua cuyo alfabeto esté compuesto únicamente por dos letras “a” y “b” cuyas oraciones son: “ab, aabb, aaabbb...” y en general todas las oraciones que constan de “n” casos de “a” seguidos de “n” casos de “b”. Notemos que en realidad estas oraciones se generan por la autoincrustación de la oración “ab” en cualquier oración precedente. Una Gramática que genera una Lengua cuyas oraciones son autoincrustantes se denomina Gramática Autoincrustante. Supongamos la existencia de una Lengua dada L1 que puede ser generada simultáneamente por varias gramáticas. Si todas estas gramáticas son autoincrustantes, la Lengua L1 se denomina Esencialmente Autoincrustante.
En cambio, una Lengua L2 que pueda ser generada tanto por una gramática autoincrustante como por una no-autoincrustante se denomina No Esencialmente Autoincrustante. Al respecto, la afirmación siguiente -que es un Teorema de la Lengua- es válida: “Un lenguaje es regular si y sólo si no es esencialmente autoincrustante”. Ello significa que la lengua generada por una gramática de estados finitos necesariamente es no autoincrustante. Si podemos demostrar que una lengua dada es esencialmente autoincrustante, habremos demostrado que no es regular. Vemos así que el inglés -Chomsky utiliza exclusivamente el inglés en sus ejemplos- y cualquier otra lengua natural tiene construcciones para cuya descripción hay que hacer uso de elementos autoincrustantes. De ahí concluye Chomsky que el inglés no es una lengua regular, lo que significa que una gramática basada en un autómata de estados finitos no puede generar todas sus oraciones adecuadamente. Esto puede tomarse como válido también para otras lenguas naturales.
Máquina Universal de Turing
Este dispositivo es denominado así debido a que su creador fue el matemático británico Alan Turing. Supongamos un dispositivo irreflexivo y absolutamente obediente, capaz de realizar cualquier tarea que le fuera encomendada. Se indica a este ingenio, dado un conjunto finito de números, encontrar cuál es el mayor de ellos, de acuerdo a las siguientes instrucciones: 1) Lea el primer número N1 del conjunto y anótelo en un dispositivo de almacenamiento (memoria), 2) Lea el siguiente número N2, 3) Compárelo con el existente en la memoria, 4) Si N2
Es decir, para cierto tipo de problemas que admiten solución, pueden definirse procedimientos que encontrarán dicha solución en un número finito de pasos. Dichos procedimientos son denominados Procedimientos Algorítmicos. A grandes rasgos, un algoritmo es un procedimiento mediante el cual podemos obtener la solución de un problema partiendo de unos datos, mediando un número finito y determinado de operaciones. De acuerdo a la concepción chomskyana de gramática, la misma no es otra cosa que un dispositivo generador de frases. Por tanto podemos decir que una gramática es un algoritmo generador de frases. El matemático Alonso Church formuló la aserción conocida como Tesis de Church, que expresa lo siguiente: “Si un proceso puede especificarse en una serie de etapas mecánicas y completamente explícitas, puede ser realizado por una Máquina Universal de Turing”. Y como las operaciones de cualquier gramática pueden ser objeto de formulaciones precisas, las mismas pueden ser generadas por una Máquina Turing. Es decir -así como el Autómata de Estados Finitos- la Máquina de Turing puede generar una gramática, y ésta a su vez, las oraciones correspondientes a la lengua L definida por ella.
Capacidad generativa de las gramáticas
Se define la capacidad generativa de una gramática como el conjunto de lenguajes factibles de ser generados por ésta. Dadas dos gramáticas G1 y G2, diremos que la capacidad generativa de G1 es mayor que la de G2 si cada lenguaje generado por G2 también puede ser generado por G1 pero no viceversa.
JerarquIa de las gramáticas. Conclusión
Una Máquina Turing puede producir una gramática capaz de generar una lengua regular pero un Autómata de Estados Finitos no tiene la capacidad generativa para producir las gramáticas factibles de ser generadas por un dispositivo Turing. Es decir, entre las gramáticas -y consecuentemente entre los autómatas- existe una jerarquía definida por la capacidad generativa. Esta jerarquía entre los autómatas, las gramáticas y las correspondientes lenguas generadas ubica a las gramáticas denominadas G0, producidas por los autómatas Turing y sus lenguas correspondientes (Lenguajes Enumerables Recursivamente) en la escala superior de capacidad generativa.
En la misma clasificación, las denominadas gramáticas G4, originadas por los autómatas de Estados Finitos (que generan las Lenguas Regulares) ocupan el último lugar.
Sólo nos queda por ubicar en la jerarquía anteriormente mencionada a las gramáticas que originan las llamadas lenguas naturales. El examen hecho de los autómatas de estados finitos y de las gramáticas de estados finitos ha probado que las lenguas naturales sobrepasan la esfera de las gramáticas del tipo G4. Otros autores afirman que las lenguas naturales deben ser consideradas -como máximo- sistemas enumerables recursivamente, lo que es decir, generadas por gramáticas G0 que tienen su origen en autómatas Turing. Ello nos lleva a concluir lo siguiente: la gramática de una lengua natural es menos general que una gramática G0 generada por una Máquina Universal de Turing pero más potente que una gramática G4 generada por un Autómata de Estados Finitos.
Enio Quevedo