En el libro de Sakarovitch sobre teoría de autómatas, está escrito en la introducción a la sección de racionales en el grupo libre que el material presentado en él establece "la base de una teoría verdaderamente matemática de lenguajes libres de contexto". Sin embargo, esto no se hace explícito, ya que los lenguajes libres de contexto y los autómatas pushdown están más allá del alcance del libro.
Soy consciente de algunas conexiones de grupos libres (y especialmente de lo que Sakarovitch llama monoides involutivos ) con la teoría de autómatas pushdown y lenguajes libres de contexto, por ejemplo, el lenguaje Dyck, el teorema de Shamir, etc. Sin embargo, he tenido un es difícil encontrar una fuente en la que se construya realmente la "teoría matemática verdadera de los lenguajes libres de contexto", mencionada por Sakarovitch.
Lo más parecido que he encontrado es el libro de Berstel sobre transducciones y lenguajes sin contexto. Sin embargo, a primera vista me parece que los autómatas pushdown se tratan solo marginalmente en este libro, mientras que la teoría de los subconjuntos racionales de un grupo libre no se aplica en absoluto. Quizás el material que estoy buscando ha sido destinado al Volumen C de Eilenberg, pero tampoco estoy seguro de eso.
Por lo tanto, me gustaría pedir un puntero a un libro, encuesta o tal vez un conjunto de documentos, del cual podría aprender algo sobre la "teoría matemática verdaderamente de los lenguajes libres de contexto" de Sakarovitch y sus relaciones con los grupos libres y su racionalidad. subconjuntos. ¿O tal vez estoy buscando algo que en realidad no existe?
fuente