Reglas de reescritura

Introducción

Veamos un poco acerca de los lenguajes formales. Esto será una introducción muy laxa, superficial y muy imprecisa. Es decir, lo vamos a ver “con manzanitas y bolitas”.

Esto puede hacer que algunas cosas difieran mucho de lo que puede decir un libro profesional sobre el tema. El objetivo no es entender los lenguajes formales sino únicamente que es una regla de reescritura.

Para comenzar, necesitamos usar el mismo vocabulario técnico, la misma terminología. Veamos poco a poco algunos términos.

Lengua

Es el conjunto de reglas que “están en la mente de una persona”¹, más el conjunto de palabras, mas sus significados.

Es sinónimo de la palabra “idioma”². Cuando estudiamos un idioma, lo que estudiamos es una lengua de un grupo de personas. Por ello podemos hablar de “lengua española”, “lengua inglesa”, “lengua nahuatl”.

Dialecto

Es una subdivisión o subconjunto de una lengua. Si pensamos que una lengua es un idioma, un dialecto es cómo un grupo de personas, divididas por cuestiones geográficas y socioeconómicas, hablan específicamente una lengua. Un dialecto es, por ejemplo “el español de la Ciudad de México” o “el español de Buenos Aires”. En computación también hay dialectos, por ejemplo Racket es un dialecto de Lisp.

Lenguaje

Definir “lenguaje” es complicado. Pensemos que existe “lenguaje de las matemáticas”, “lenguaje del amor”, “lenguaje no verbal”, “lenguaje computacional”, etc. El lenguaje es todo sistema humano abstracto que está estructurado. Su función es ser usado y expresar cosas –pero no necesariamente es para la comunicación–. Un lenguaje es el conjunto de expresiones que usa un grupo y que están ligadas a su forma de vida. La danza sería un lenguaje, las matemáticas serían un lenguaje, la vestimenta sería un lenguaje…

Lenguaje formal

Es un tipo de lenguaje donde no nos interesan los significados sino la forma de sus expresiones. En este tipo de lenguajes la sintaxis es más importante que la semántica; es decir, importa más como se combinan sus elementos que lo que significan. Su uso está en cómo se combinan las expresiones de manera de que podemos saber si una expresión pertenece o no al lenguaje.

Entonces, para esta explicación únicamente, el lenguaje es un conjunto enorme de todas las formas en las que se usan las expresiones. Dentro de él, habría conjuntos más pequeños que serían las lenguas –por ejemplo, el español–. Un dentro de cada lengua habría más conjuntos pequeños que serían los dialectos.

Símbolos y cadenas

La unidad menor de los lenguajes formales es el símbolo. El símbolo, para nosotros, es cualquier elemento gráfico que no tenga significado. Dado que no tienen significado, los símbolos se pueden usar arbitrariamente –es decir, cualquiera, sin que importe cual– a menos de que en las reglas del lenguaje se diga lo contrario.

Un símbolo, entonces, podría ser

X

aquí, por ejemplo, tenemos cuatro símbolos

abwx

incluso los símbolos pueden ser los siguientes

✇ ♥ ⚥ ✪ ♩ ☻

son seis símbolos. No nos interesa su significado en lo absoluto. Para nosotros, son solo como piezas de LEGO. Son bloques con los que vamos a armar estructuras.

Las estructuras que arman los símbolos se les llama cadenas. Las cadenas son secuencias lineales de símbolos. Si vemos una línea de símbolos, uno atrás del otro, en “fila” es una cadena; hay que pensar en los símbolos como eslabones.

Entonces una cadena podría ser como

aabababbabababa

también como

lkjshdñlsakjhñsljkfhioeu

ya que cualquier elemento gráfico es un símbolo, una cadena podría ser

(())()((()())))(()(()((()))())((())))

también

♥♥♥♥♥♥

no importa el tamaño de la cadena, una cadena válida, de un solo símbolo, podría ser

X

Podemos pensar de la siguiente manera: Los símbolos son las palabras de los lenguajes formales; las cadenas son los enunciados.

Tenemos un problema con eso, sabemos que el español es una lengua, y una lengua es un subconjunto de los lenguajes³. Pero si los símbolos son las palabras, en español las palabras parecen cadenas –o, mejor dicho, subcadenas–.

Existen una serie de símbolos especiales que vamos a llamar metasímbolos. Estos símbolos no sirven para crear cadenas en el lenguaje, sino que nos dicen “como suceden ciertas cosas” o “cómo se debe interpretar algo”.

En español, por ejemplo, tenemos el metasímbolo llamado signo de interrogación:

?

No es parte de cómo se combinan las palabras, sino nos dice que el enunciado es una pregunta.

Otro metasímbolo que tenemos en la escritura en español es el espacio en blanco. El espacio en blanco marca cuando una palabra inicia y termina. Es decir, el espacio en blanco es un metasímbolo que indica “todo lo que esté entre uno y otro, consideralo un solo símbolo”.

Nosotros nos vamos a usar un metasímbolo específico. Es la barra vertical:

|

Pudimos elegir cualquier otro símbolo, pero la barra servirá. Ella indicará que todo lo que esté entre dos de ellos se debe considerar un sólo símbolo.

Es decir, si tenemos

SUSTANTIVO

podemos decir que se trata de una cadena con diez símbolos. Pero si tenemos

|SUSTANTIVO|

para nosotros es una cadena con un sólo símbolo. Igual si tenemos una cadena como

El perro corre

decimos que es una cadena con catorce símbolos –incluidos espacios en blanco–. Pero si tenemos

|El||perro||corre|

para nosotros es una cadena con tres símbolos, tendría la misma longitud que

abb

Otro metasímbolo que nos será útil serán aquellos que conforman una lista. Para decir que algo está en lista, pondremos todo entre corchetes y separado por comas. Es decir, si tenemos esto:

[a,b,c,d]

lo que realmente significa es que tenemos esto

• a
• b
• c
• d

o si tenemos esto

[|árbol|,|manzana|,|sol|]

lo que realmente tenemos es esto

• árbol
• manzana
• sol

Un último metasímbolo que nos será útil serán las comillas. Para nosotros todo lo que esté entre comillas será una cadena:

"Esto es una cadena"
"kjhñdsahdoifhpsodf"

ambas son cadenas dentro de un lenguaje.

Sintaxis y paradigma

Dicho esto, hay dos características del lenguaje humano que debemos revisar: las relaciones sintagmáticas y paradigmáticas.

La sintaxis no es otra cosa que saber si una cadena está bien construida basándonos en la combinatoria de los símbolos. Pensemos que tenemos los siguientes símbolos:

[|el|,|la|,|perro|,|niña|,
|come|,|canta|,|carne|,|bonito|]

podemos construir las cadenas

"|el||perro||come||carne|"
"|la||niña||canta||bonito|"

pero si construimos cadenas como

"|come||la||el||carne|"
°|bonito||la||perro||carne|"

hay algo que no está bien.

Esto ha nos ha intrigado durante los últimos 100 años En gran parte, por las investigaciones de Noam Chomsky durante los años 50. . ¿Cómo es que nuestra mente, sin pensarlo, puede combinar palabras de manera que estén “bien construidas”?, ¿cómo es que nunca nos equivocamos?, ¿cómo es que los bebés y niños adquieren esto?

Algo que hay que notar es que la sintaxis es la combinatoria “en presencia”: evaluamos si una vez construida la cadena es aceptable en el lenguaje.

También tenemos relaciones “en ausencia”: es decir, cómo es que se combinan las palabras antes de formar la cadena. Esto se les llama paradigmas.

Las relaciones paradigmáticas es por qué palabra se puede sustituir otra sin que afecte la sintaxis. Pensemos que tenemos una cadena como “la niña come sandía”. Cada palabra puede sustituida por muchas otras:

Como vemos, “niña” puede ser sustituida paradigmáticamente por cualquier palabra del español siempre y cuando sea singular y femenina. El paradigma de “niña” es el mismo que el de “sandía” así que son intercambiables⁴. Sin embargo, “niña” no podía ser sustituida por “pelotas” o “soldado” porque la sintaxis se afectaría.

Reglas de reescritura

En la teoría de los lenguajes formales podemos pensar que hay dos intereses principales:

1. Cuáles cadenas son aceptables en un lenguaje dado;
2. Cómo se generan las cadenas de un lenguaje dado.

Solo nos interesa a nosotros la segunda, cómo se generan las cadenas. Para generar cadenas, debemos establecer una gramática. Una gramática es el conjunto de reglas sintácticas para generar cadenas⁵.

La gramática que construiremos es por medio de reglas de reescritura. Las reglas de reescritura se presentan por el metasímbolo

→	

Una flecha apuntando a la derecha. También se representa con dos puntos.

: 

Una regla de reescritura se ve así:

A → B

o así

B:a

Una gramática se vería así:

C → B
B → a
X → CC

La cual sería una gramática con tres reglas. Hay dos formas de entender esa flecha, tú elige la que sea más conveniente para ti –aunque la usual es la primera–. La flecha de reescritura significa:

A → B

o

“Si encuentras el símbolo A en una cadena, bórralo y escribe el símbolo B en su lugar”

otra manera de pensar esta flecha es

Para obtener el símbolo B, debes tener una cadena que tenga el símbolo A.

  entonces, piensa que tienes una regla que dice lo siguiente

b → x

esto quiere decir “si encuentras una b, borrala y reescribe una x en su lugar”. Otra forma sería “para obtener una b , necesitas que haya una x primero”. Imagina que, ya que tienes esa regla, te dan una cadena así :

aabaa

si tu aplicas la regla, lo que sucede es que te quedas con una cadena así:

aaxaa

Algo que podríamos preguntarnos es ¿por qué no cambiaron las ‘a’?

Como sólo teníamos una regla “b → x”, ningún símbolo “a” aparecía a ‘a la izquierda’ de la flecha. Por eso el resto de la cadena se quedó intacta.

Es decir, una regla de reescritura sólo afecta al símbolo que hay “a la izquierda” de la regla en las cadenas y los demás símbolos de la cadena los deja intactos.

Axiomas, terminales y no terminales

La generación de cadenas nunca puede iniciar de la nada. No puedes tener cero o el conjunto vacío para iniciar la generación de una cadena. Las cadenas inician desde un símbolo inicial especial el cual llamaremos axioma.

El axioma es un símbolo que no puede producirse con reglas previas. Siempre es nuestro punto de origen. Tradicionalmente, el símbolo que se usa es la letra “S” mayúscula –por start– o la letra “o” mayúscula –por origen u oración–. Nosotros usaremos la letra “O” mayúscula para indicar que ese es el axioma. Por lo tanto, toda gramática que realicemos debe iniciar con la regla

O → ...

A partir de allí los símbolos se van a dividir en dos tipos: terminales y no terminales.

Los símbolos no terminales, como su nombre lo indica, no terminan en la cadena generada. Nunca aparecen en la cadena final –por eso son no terminales–. Podemos pensarlos como que solo sirven ‘de puente’ para ‘brincar’ a los terminales. Si tenemos unas reglas como

O → B
B → n

de hecho lo que tenemos es una regla así

O → B → n

lo cual podríamos hasta simplificar como

O → n

En este caso, el símbolo ‘B’ seria no terminal, ya que solo se usa para llegar de ‘O hasta ‘n’. Estos no terminales se representan, tradicionalmente, con letras mayúsculas para identificarlos. Nosotros seguiremos esa regla: los no-terminales serán siempre mayúsculas para saber que seguirán cambiando.

Los símbolos terminales son aquellos cuya regla es para llegar a simbolos que sí estarán dentro de nuestra cadena.

Los símbolos terminales son aquellos que no tienen una regla ‘a la izquierda’ de la flecha. En el ejemplo anterior, vemos que no hay una regla asi

n → ... 

Por lo cual sabemos que ‘n’ es no terminal. Usualmente se ponen en minúscula para identificarlos más rápidamente. Una vez que aparecen en la cadena, ya no se puede hacer más reescritura.

Los símbolos terminales los podemos ver como variables. Una variable es un símbolo que tiene un valor asociado. Piensa en ellos como una “cajita” donde tu le puedes meter cualquier objeto o valor y, al final que construyes la cadena, puedes abrir la caja a ver que contiene.

Todo esto puede parecer muy oscuro. Hagamos un ejemplo para ver que significa todo esto. Pensemos que tenemos la gramática:

O → XYX
X → a
Y → b

Podemos ser más formales, y numerar cada regla para saber cuál estaremos aplicando en cada paso, de esta forma:

R1. O → XYX
R2. X → a
R3. Y → b

Ahora veremos cómo se juega esto. Consideremos que la cadena de inicio es:

"O"

es decir, el axioma. Una cadena de un solo símbolo. ¿Cómo quedaría una vez que se le apliquen las reglas de nuestra gramática?

Como vemos, [a,b] son signos no terminales ya que no aparecen del lado izquierdo, así que cuando aparezcan, ya no se puede reescribir más. Los símbolos [Y,X] son no terminales, así que no aparecerán al final en nuestra cadena generada. Si aplicamos una por una las reglas:

¿Qué pasaría si “a” fuera una variable que significa “corre” y “b” fuera una variable con contenido “perro”?

a = corre
b = perro

aba = "corre perro corre"

Todo lo que hemos hecho hasta el momento lo llamaremos –aunque no sea exacto– una formalización. Formalizar solo es poner en símbolos sistemas complejos –como el lenguaje– de manera que su forma sea más clara.

Oración simple

Para este momento, una pregunta puede ser “¿qué tiene que ver todo esto con la navidad?”, es decir, ¿esto que tiene que ver con lo que haremos?.

Vamos a intentar hacer la gramática de una oración simple –intransitiva–. Algo como:

“El perro amarillo camina lento”

¿Cómo podemos obtener esa oración con un axioma O? Podemos hacer trampa, primero generando una cadena de tres elementos y luego cada elemento es una variable para cada palabra. Pero la cuestión es más compleja.

Comenzemos etiquetando cada palabra por su forma y función. En las oraciones simples hay dos palabras importantes: el verbo y el nombre –solía llamarse sustantivo–. Estas palabras tienen algo llamado “contenido léxico”, es decir, son conceptuales, podemos pensar en ellas aunque sean abstractas. Vamos a ubicarlas.

“El perro amarillo camina lento”
    --^--          --^-- 
    Nombre         Verbo

Luego de eso tenemos palabras que lo que hacen es decir características de las palabras con contenido léxico. No podemos pensar en ellas más que añadiéndolas a ellas. Son el adjetivo –dice características sobre el nombre y el adverbio –dice características del verbo–.

“El perro amarillo camina lento”
    --^--  ---^--  --^--  --^--
   Nombre Adjetivo Verbo  Adverbio

En las oraciones hay “trozos” mas pequeños, subsecciones. Se forman cuando combinamos sintácticamente palabras y, juntas, tienen una relación paradigmática con construcciones similares.

Estos trozos los llamaremos ‘frases’ y éstas estarán dominadas por la palabra que no se pueda cambiar paradigmaticamente⁶.

Por ejemplo, en la relación “nombre-adjetivo” podemos intercambiarlo:

El gato negro camina lento

también la combinación “verbo-adverbio”:

El perro amarillo come mucho

¿Quién domina?, ¿El nombre y el verbo, o el adjetivo y el adverbio? Podemos, paradigmáticamente, hacer las mismas oraciones sin adjetivo o adverbio:

El gato camina lento

y

El perro come mucho

pero no podemos tener

El amarillo camina lento

o

El perro mucho

ya que cambia totalmente el sentido y la sintaxis. Así que tenemos un par de frases: una “frase nominal” y una “frase verbal”.

“El perro amarillo   camina lento”
    --^--  ---^--     --^--  --^--
   Nombre Adjetivo   Verbo  Adverbio
   ------^-------    ------^------
    Frase Nominal     Frase Verbal

Nos falta la palabra “el”. Es un determinante, ya que determina cuál nombre es –solía llamarse artículo–. El determinante crea toda una frase que puede ser cambiada paradigmáticamente:

Un anciano uruguayo camina lento

así que tenemos una “frase determinante”

“El perro amarillo   camina lento”
    --^--  ---^--     --^--  --^--
   Nombre Adjetivo   Verbo  Adverbio
   ------^-------    ------^------
    Frase Nominal     Frase Verbal
-------^----------
Frase Determinante

Finalmente, como ya no hay más que analizar, pues solo queda la oración

“El perro amarillo   camina lento”
    --^--  ---^--     --^--  --^--
   Nombre Adjetivo   Verbo  Adverbio
   ------^-------    ------^------
    Frase Nominal     Frase Verbal
-------^----------
Frase Determinante      
------------------^---------------
            Oración

Cambiemos todo por símbolos más cortos, porque somos flojos para escribir

“El perro amarillo   camina lento”
    --^--  ---^--     --^--  --^--
     |N|    |ADJ|      |V|  |ADV|
   ------^-------    ------^------
         |FN|             |FV|
-------^----------
        |FD|
------------------^---------------
                |O|

De hecho, esto es un “árbol”. Pero eso lo veremos en otra ocasión.

Para hacer la gramática de esto, tendríamos que comenzar por |O| y seguir así en las reglas. La primera sería una regla que reescriba |O| como |FD| y |FV|, y continuar así:

1. |O|   →  |FD| |FV|
2. |FD|  →  |D| |FN|
3. |FN|  →  |N| |ADJ|
4. |FV|  →  |V| |ADV|
5. |D|   →  'el'
6. |N|   →  'perro'
7. |ADJ| →  'amarillo'
8. |V|   →  'camina'
9. |ADV| →  'lento'

  Y podemos comprobar que la gramática cumple su función al aplicar las reglas.

Dada una cadena inicial “O” y con axioma “O”:

Por concatenación:

“El perro amarillo camina lento”

Esto suena terrible. Parece que tendríamos que hacer una gramática para cada palabra que escribamos.

Vamos a aprovecharnos de que se pueden hacer variables y que la gramática es sensible al contexto. Piensa en una gramática así:

O → “Mañana voy a comer |COMIDA|”
|COMIDA| → "tamales"

Esta gramática da como resultado:

“Mañana voy a comer tamales”

Hay varias cosas que apuntar. Hay que recordar que las comillas son metasímbolos que indican “todo esto es una cadena”. Con ello, solo busca los símbolos que se pueden reescribir y que tienen una regla asociada, en este caso, |COMIDA|.

Podemos meter en ese símbolo una lista –ya que cualquier símbolo puede ser una variable–. En este caso, puede haber una gramática así:

O → “Mañana voy a comer |COMIDA|”
|COMIDA| → ["tamales","pozole","tacos"]

Aleatoriamente, obtendríamos una cadena como

“Mañana voy a comer tacos”

Esto se puede usar para hacer un bot literario. También puede explicar cierta teoría de la mente y el lenguaje. Esto también puede servir para otras cosas más interesantes, pero eso es para otro momento.

Notas