¿Se pueden usar los lenguajes formales para estudiar la notación matemática?

Pregunta: ¿Hay algún texto introductorio en lenguaje formal o teoría del lenguaje de programación que discuta cómo aplicarlo al estudio de la notación óptima?

En particular, estoy interesado en aprender qué son los lenguajes de pila, los árboles de análisis y los índices, y cómo predecir cuándo un cierto tipo de notación conducirá a una redundancia exponencial.

Básicamente no tengo experiencia en lenguaje formal / gramática o teoría de programación, ya que como estudiante de matemáticas, la única ciencia de la computación que aprendí fue algoritmos y teoría de grafos, así como pequeños pilares de teoría de la complejidad y funciones booleanas. Por lo tanto, si los únicos libros que discuten esto no son introductorios, agradecería las respuestas que enumeren tales libros que analizan la explosión de la notación exponencial, así como los libros introductorios que se prepararán para los libros que abordan directamente mi pregunta.

Contexto: esta pregunta está inspirada principalmente en una respuesta en Physics.SE , que dice que:

Es muy fácil demostrar (rigurosamente) que no hay notación de paréntesis que reproduzca las contracciones del índice tensorial, porque los paréntesis son analizados por un lenguaje de pila (gramática libre de contexto en la clasificación de Chomsky), mientras que los índices no pueden analizarse de esta manera, porque incluyen gráficos Los paréntesis generan árboles de análisis, y siempre tiene exponencialmente muchos árboles máximos dentro de cualquier gráfico, por lo que hay una redundancia exponencial en la notación.

En el resto de la respuesta, se discuten otros ejemplos de "explosión de notación exponencial", por ejemplo, con redes de Petri en biología computacional.

También hay otros casos en los que la notación matemática es difícil de analizar, por ejemplo, como se menciona aquí cuando las funciones y las funciones aplicadas al argumento no se distinguen claramente. Esto puede volverse especialmente confuso cuando la función se convierte en argumento y el argumento se convierte en función, por ejemplo, aquí .

1. La teoría formal del lenguaje no se ocupa de la semántica del lenguaje. Puede parecer extraño, ya que tendemos a pensar en el lenguaje como un mecanismo para comunicar algo, pero si lo piensas, en realidad hay dos niveles de comprensión del lenguaje (al menos): el nivel superficial, en el que el lenguaje es un flujo de lexemas, y el nivel de denotación subyacente que está más o menos divorciado de la representación superficial. (Chomsky postuló un nivel intermedio "transformacional" para sortear algunas limitaciones con los CFG pero eso no es relevante aquí.) En consecuencia, es posible decir "lo mismo" en diferentes idiomas; Chomsky no es un whorfiano. (Ver Wikipedia para una breve descripción, con algunas referencias).

2. Sin embargo, una gramática libre de contexto no es suficiente para distinguir las expresiones correctas e incorrectas. Chomsky ofreció el ejemplo clásico: las ideas incoloras duermen furiosamente (lo que deletreó incorrectamente, siendo estadounidense). Ver Wikipedia , nuevamente. (Desafortunadamente, Wikipedia no tiene una versión en inglés canadiense). La división precisa entre los errores sintácticos y semánticos es difícil, si no imposible, demarcar y ha habido un debate considerable sobre este tema en los campos de CS, que no voy a analizar. incluso intento discutir aquí porque siempre me meto en problemas cuando lo hago. Sin embargo, podemos identificar una regla gramatical clásica presente en muchos idiomas humanos: acuerdo sustantivo / verbo. No estoy de acuerdoMe parece un error sintáctico en el sentido de que entiendo perfectamente la intención de la expresión pero también la reconozco como errónea. Pero este problema sintáctico solo puede ser capturado por una gramática libre de contexto si enumeramos todos los acuerdos posibles. Es decir, podemos escribir algo vagamente como$S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, pero es fácil ver cómo la enumeración podría salirse de control en un lenguaje con reglas de acuerdo más complicadas (género, por ejemplo).

3. El problema con las gramáticas libres de contexto es que están libres de contexto, aunque no debería tomarse esa descripción demasiado en serio porque es fácil caer en la trampa de malinterpretar el uso técnico de palabras comunes (lo cual, podría argumentar, es el base de esta pregunta en primer lugar). Eso significa que un no terminal (como$NP$arriba) debe derivar exactamente el mismo conjunto de frases independientemente del contexto en el que aparece. Entonces no pudimos escribir, por ejemplo,$S \to NP_X VP_X$ con el entendimiento de que $X$necesita ser llenado de la misma manera en ambas expansiones. (Este es uno de los problemas que la gramática transformacional intentó resolver).

4. Ese es exactamente el problema con las contracciones del índice tensorial. Una contracción del índice tensorial impone un requisito particular en el uso de variables de índice: una variable de índice debe usarse exactamente dos veces, en cuyo caso no puede estar en el lado izquierdo, o exactamente una vez, en el que debe estar en el lado izquierdo. lado. (Como no soy físico, me vería tentado a colapsar y decir que una variable de índice debe aparecer exactamente dos veces en total. Pero existe una distinción semántica entre las variables libres y las de marcador de posición, lo cual es importante para comprender el expresión.) Aquí, no existe una colección finita simple de variables de índice y no hay límite para el número de marcadores de posición utilizados. Además, cambiar el nombre de los marcadores de posición no afecta a la semántica siempre que los nuevos nombres no se usen en otra parte de la expresión,

5. De hecho, es posible probar rigurosamente la afirmación de que las gramáticas libres de contexto no pueden capturar un acuerdo contextual, como en los ejemplos anteriores. Creo que eso tiene algo que ver con lo que afirma la afirmación citada. Dependiendo de lo omnívoro que seas, puede que te resulte interesante aprender más, pero no creo que termine siendo particularmente relevante para las ideas filosóficas o físicas que pareces estar buscando.

6. Los otros artículos vinculados, sobre formas superficiales desafortunadas en notación matemática, son simplemente anecdóticos; ninguno de ellos, por lo que puedo ver, hace que ningún punto profundo o incluso superficial sea relevante para la teoría del lenguaje formal, al igual que la posible broma famosa de que el pez de un hombre es el poisson de otro hombre ni siquiera es vagamente perspicaz sobre la lingüística romántica, pero sigue siendo divertido (IMO)