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