Les langages formels peuvent-ils être utilisés pour étudier la notation mathématique?

Question: Existe-t-il des textes d'introduction en langage formel ou en théorie du langage de programmation qui discutent de la façon de l'appliquer à l'étude de la notation optimale?

En particulier, je suis intéressé à savoir quels sont les langages de pile, les arbres d'analyse et les indices, et comment prédire quand un certain type de notation entraînera une redondance exponentielle.

Je n'ai pratiquement aucune expérience en langage formel / grammaire ou en théorie de la programmation, car en tant que mathématicien, la seule informatique que j'ai apprise était les algorithmes et la théorie des graphes, ainsi que de très modestes notions de théorie de la complexité et de fonctions booléennes. Ainsi, si les seuls livres qui en discutent ne sont pas introductifs, je serais reconnaissant pour les réponses qui répertorient tous les deux des livres traitant de l'explosion de la notation exponentielle ainsi que des livres d'introduction qui prépareront les livres qui répondent directement à ma question.

Contexte: Cette question s'inspire principalement d' une réponse sur Physics.SE , qui dit que:

Il est très facile de prouver (rigoureusement) qu'il n'y a pas de notation entre parenthèses qui reproduit les contractions d'index du tenseur, car les parenthèses sont analysées par un langage de pile (grammaire sans contexte dans la classification de Chomsky) tandis que les indices ne peuvent pas être analysés de cette façon, car ils incluent des informations générales graphiques. Les parenthèses génèrent des arbres d'analyse, et vous avez toujours de façon exponentielle de nombreux arbres maximaux à l'intérieur de n'importe quel graphique, il y a donc une redondance exponentielle dans la notation.

Dans le reste de la réponse, d'autres exemples de "explosion de notation exponentielle" sont discutés, par exemple avec des réseaux de Petri en biologie computationnelle.

Il existe également d'autres cas où la notation mathématique est difficile à analyser, par exemple comme mentionné ici lorsque les fonctions et les fonctions appliquées à l'argument ne sont pas clairement distinguées. Cela peut devenir particulièrement déroutant lorsque la fonction devient l'argument et l'argument devient la fonction, par exemple ici .

1. La théorie du langage formel ne se préoccupe pas de la sémantique du langage. Cela peut sembler étrange, car nous avons tendance à penser la langue comme un mécanisme de communication, mais si vous y réfléchissez, il y a vraiment deux niveaux de compréhension de la langue (au moins): le niveau de surface, dans lequel la langue est un flux des lexèmes, et le niveau dénotationnel sous-jacent qui est plus ou moins dissocié de la représentation de surface. (Chomsky a proposé un niveau «transformationnel» intermédiaire pour contourner certaines limitations des CFG, mais ce n'est pas pertinent ici.) Par conséquent, il est possible de dire «la même chose» dans différentes langues; Chomsky n'est pas un Whorfian. (Voir Wikipedia pour un bref aperçu, avec quelques références).

2. Néanmoins, une grammaire sans contexte n'est pas suffisante pour distinguer les énoncés corrects et incorrects. Chomsky a donné l'exemple classique: les idées incolores dorment furieusement (qu'il a mal orthographié, étant un USian). Voir à nouveau Wikipédia . (Malheureusement, Wikipedia n'a pas de version canadienne-anglaise.) La division précise entre les erreurs syntaxiques et sémantiques est difficile, sinon impossible, à délimiter et il y a eu un débat considérable sur ce sujet dans les domaines CS, que je ne vais pas aborder. même essayer de discuter ici parce que j'ai toujours des ennuis quand je le fais. Cependant, nous pouvons identifier une règle grammaticale classique présente dans de nombreuses langues humaines: l'accord nom / verbe.Je ne suis pas d'accordme semble être une erreur syntaxique dans le sens où je comprends parfaitement l'intention de l'énoncé mais que je le reconnais également comme erroné. Mais ce problème syntaxique ne peut être capturé par une grammaire hors contexte que si nous énumérons tous les accords possibles. Autrement dit, nous pouvons écrire quelque chose comme vaguement$S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, mais il est facile de voir comment l'énumération pourrait devenir incontrôlable dans un langage avec des règles d'accord plus compliquées (genre, par exemple).

3. Le problème avec les grammaires sans contexte est qu'elles sont sans contexte, bien que vous ne deviez pas prendre cette description trop au sérieux car il est facile de tomber dans le piège d'une mauvaise interprétation technique de mots courants (ce qui, je dirais, est le base de cette question en premier lieu). Cela signifie qu'un terminal non terminal (comme$NP$ci-dessus) doit dériver exactement le même ensemble de phrases quel que soit le contexte dans lequel il apparaît. Nous n'avons donc pas pu écrire, par exemple,$S \to NP_X VP_X$ étant entendu que $X$doit être rempli de la même manière dans les deux extensions. (C'est l'un des problèmes que la grammaire transformationnelle a tenté de résoudre.)

4. C'est exactement le problème des contractions d'indice de tenseur. Une contraction d'indice tensoriel impose une exigence particulière sur l'utilisation des variables d'index: une variable d'index doit être utilisée exactement deux fois, auquel cas elle ne peut pas être sur le côté gauche, ou exactement une fois, dans laquelle elle doit être sur la gauche- côté. (Étant donné que je ne suis pas physicien, je serais tenté de résumer cela en disant qu'une variable d'index doit apparaître exactement deux fois en tout. Mais il existe une distinction sémantique entre les variables libres et les variables fictives, ce qui est important pour la compréhension de la expression.) Ici, il n'y a pas de collection finie simple de variables d'index et pas de limite au nombre d'espaces réservés utilisés. De plus, renommer les espaces réservés n'affecte pas la sémantique à condition que les nouveaux noms ne soient pas utilisés ailleurs dans l'expression,

5. Il est en effet possible de prouver rigoureusement l'affirmation selon laquelle les grammaires sans contexte ne peuvent pas capturer l'accord contextuel, comme dans les exemples précédents. Je pense que cela a quelque chose à voir avec ce que la revendication citée affirme. En fonction de votre omnidiction, vous trouverez peut-être intéressant d'en savoir plus, mais je ne pense pas que cela finira par être particulièrement pertinent pour les idées philosophiques ou physiques que vous semblez rechercher.

6. Les autres articles liés, sur les formes de surface malheureuses en notation mathématique, sont simplement anecdotiques; pour autant que je sache, aucun d'entre eux ne soulève de point profond ou même superficiel pertinent pour la théorie du langage formel, tout comme la blague peut-être célèbre selon laquelle le poisson d'un homme est le poisson d' un autre n'est même pas vaguement révélatrice de la linguistique romanesque, mais c'est toujours drôle (OMI).