Linguagens formais podem ser usadas para estudar notação matemática?

Pergunta: Existem textos introdutórios na linguagem formal ou na teoria da linguagem de programação que discutam como aplicá-la ao estudo da notação ideal?

Em particular, estou interessado em aprender o que são linguagens de pilha, árvores de análise e índices e como prever quando um determinado tipo de notação levará a redundância exponencial.

Basicamente, não tenho formação em linguagem formal / gramática ou teoria de programação, pois, como especialista em matemática, a única ciência da computação que aprendi foram algoritmos e teoria de grafos, bem como smidgens muito modestas da teoria da complexidade e das funções booleanas. Assim, se os únicos livros que discutem isso não forem introdutórios, eu ficaria grato pelas respostas que listam esses livros que discutem a explosão de notação exponencial, bem como livros introdutórios que se preparam para os livros que abordam diretamente minha pergunta.

Contexto: Esta pergunta é inspirada principalmente por uma resposta no Physics.SE , que diz que:

É muito fácil provar (rigorosamente) que não há notação entre parênteses que reproduz contrações no índice tensorial, porque os parênteses são analisados ​​por uma linguagem de pilha (gramática livre de contexto na classificação de Chomsky) enquanto os índices não podem ser analisados ​​dessa maneira, porque incluem gráficos. Os parênteses geram árvores de análise e você sempre tem muitas árvores máximas exponencialmente em qualquer gráfico, portanto, existe uma redundância exponencial na notação.

Em todo o restante da resposta, outros exemplos de "explosão de notação exponencial" são discutidos, por exemplo, com redes de Petri em biologia computacional.

Há também outros casos em que a notação matemática é difícil de analisar, por exemplo, como mencionado aqui, quando funções e funções aplicadas ao argumento não são distinguidas claramente. Isso pode se tornar especialmente confuso quando a função se torna o argumento e o argumento se torna a função, por exemplo, aqui .

1. A teoria formal da linguagem não se preocupa com a semântica da linguagem. Isso pode parecer estranho, já que tendemos a pensar na linguagem como um mecanismo de comunicação de algo, mas se você pensar bem, existem realmente dois níveis de entendimento da linguagem (pelo menos): o nível da superfície, no qual a linguagem é um fluxo de lexemas e o nível denotacional subjacente que é mais ou menos divorciado da representação superficial. (Chomsky colocou um nível "transformacional" intermediário para contornar algumas limitações dos CFGs, mas isso não é relevante aqui.) Consequentemente, é possível dizer "a mesma coisa" em diferentes idiomas; Chomsky não é um whorfiano. (Veja Wikipedia para uma breve visão geral, com algumas referências).

2. No entanto, uma gramática livre de contexto não é suficiente para distinguir enunciados corretos e incorretos. Chomsky ofereceu o exemplo clássico: idéias incolores dormem furiosamente (que ele soletrou incorretamente, sendo um americano). Veja a Wikipedia novamente. (Infelizmente, a Wikipedia não possui uma versão em inglês canadense.) É difícil demarcar a divisão precisa entre erros sintáticos e semânticos, e se não é impossível demarcar, e houve um debate considerável sobre esse tópico nos campos de CS, que não vou abordar. até tente discutir aqui, porque sempre encontro problemas quando o faço. No entanto, podemos identificar uma regra gramatical clássica presente em muitas línguas humanas: concordância substantivo / verbo. Eu discordoparece-me um erro sintático no sentido de entender perfeitamente a intenção do enunciado, mas também reconhecê-lo como errôneo. Mas esse problema sintático só pode ser capturado por uma gramática livre de contexto se enumerarmos todos os acordos possíveis. Ou seja, podemos escrever algo vagamente como$S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, mas é fácil ver como a enumeração pode ficar fora de controle no idioma com regras de contrato mais complicadas (gênero, por exemplo).

3. O problema das gramáticas sem contexto é que elas não têm contexto, embora você não deva levar essa descrição muito a sério, porque é fácil cair na armadilha de interpretar mal o uso técnico de palavras comuns (que, devo argumentar, é a base desta questão). Isso significa que um não-terminal (como$NP$acima) deve derivar exatamente o mesmo conjunto de frases, independentemente do contexto em que aparece. Então não conseguimos escrever, por exemplo,$S \to NP_X VP_X$ com o entendimento de que $X$precisa ser preenchido da mesma maneira nas duas expansões. (Esse é um dos problemas que a gramática transformacional tentou entender.)

4. Esse é exatamente o problema com as contrações no índice tensorial. Uma contração de índice tensorial impõe um requisito específico ao uso de variáveis ​​de índice: uma variável de índice deve ser usada exatamente duas vezes; nesse caso, não pode estar no lado esquerdo ou exatamente uma vez, no qual deve estar no lado esquerdo. lado da mão. (Como não sou físico, ficaria tentado a dizer que uma variável de índice deve aparecer exatamente duas vezes ao todo. Mas há uma distinção semântica entre variáveis ​​livres e de espaço reservado, o que é importante para a compreensão do ). Aqui, não existe uma coleção finita simples de variáveis ​​de índice e não há limite para o número de espaços reservados usados. Além disso, a renomeação de espaços reservados não afeta a semântica, desde que os novos nomes não sejam usados ​​em outras partes da expressão,

5. É de fato possível provar rigorosamente a afirmação de que gramáticas sem contexto não podem capturar concordância contextual, como nos exemplos anteriores. Eu acho que isso tem algo a ver com o que a afirmação citada está afirmando. Dependendo de como você é omnicioso, você pode achar interessante aprender mais, mas não acho que isso acabe sendo particularmente relevante para os insights filosóficos ou físicos que você parece estar procurando.

6. Os outros artigos vinculados, sobre formas infelizes de superfície em notação matemática, são simplesmente anedóticos; nenhum deles, até onde eu posso ver, faz qualquer ponto profundo ou até superficial relevante para a teoria formal da linguagem, assim como a piada possivelmente famosa de que o peixe de um homem é o poisson de outro homem nem sequer é vagamente perspicaz sobre a lingüística do romance, mas ainda é engraçado (IMO).