No livro de Sakarovitch sobre a teoria dos autômatos, está escrito na introdução à seção sobre racionais no grupo livre que o material apresentado nele estabelece "o fundamento de uma teoria verdadeiramente matemática das linguagens livres de contexto". No entanto, isso não é explicitado, pois linguagens sem contexto e autômatos de empilhamento estão além do escopo do livro.
Estou ciente de algumas conexões de grupos livres (e especialmente do que Sakarovitch chama de monoides involutivos ) à teoria dos autômatos de empilhamento e das linguagens livres de contexto - por exemplo, a linguagem Dyck, o teorema de Shamir, etc. dificuldade em encontrar uma fonte na qual a "teoria verdadeiramente matemática das linguagens livres de contexto", mencionada por Sakarovitch, seja realmente construída.
A coisa mais próxima que encontrei é o livro de Berstel sobre transduções e linguagens livres de contexto. Contudo, à primeira vista, parece-me que os autômatos de empilhamento são tratados apenas marginalmente neste livro, enquanto a teoria dos subconjuntos racionais de um grupo livre não é aplicada. Talvez o material que estou procurando tenha sido destinado ao volume C de Eilenberg, mas também não tenho certeza.
Então, eu gostaria de pedir um ponteiro para um livro, pesquisa ou talvez um conjunto de artigos, dos quais eu pudesse aprender algo sobre a "verdadeira teoria matemática das linguagens livres de contexto" de Sakarovitch e suas relações com grupos livres e sua racionalidade. subconjuntos. Ou talvez eu esteja procurando por algo que realmente não existe?
fonte