В книге Сакаровича по теории автоматов во введении к разделу о рациональных числах в свободной группе написано, что представленный в нем материал закладывает «основу действительно математической теории языков без контекста». Тем не менее, это не указывается явно, так как языки без контекста и автоматные выпадающие программы выходят за рамки книги.
Я знаю о некоторых связях свободных групп (и особенно о том, что Сакарович называет инволютивными моноидами ) с теорией автоматов и контекстно-свободных языков - например, язык Дейка, теорема Шамира и т. Д. Однако у меня был трудно найти источник, в котором фактически была бы создана «действительно математическая теория контекстно-свободных языков», упомянутая Сакаровичем.
Самая близкая вещь, которую я нашел, - это книга Берстеля о трансдукциях и языках без контекста. Однако, на первый взгляд, мне кажется, что в этой книге автоматы выталкивания рассматриваются лишь незначительно, в то время как теория рациональных подмножеств свободной группы вообще не применяется. Возможно, материал, который я ищу, был предназначен для Тома Эйленберга, но я в этом тоже не уверен.
Поэтому я хотел бы попросить дать указатель на книгу, обзор или, возможно, набор статей, из которых я мог бы кое-что узнать о «истинно математической теории безконтекстных языков» Сакаровича и ее отношении к свободным группам и их рациональному подходу. подмножества. Или, может быть, я ищу то, чего на самом деле не существует?
источник