лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.Затронуты следующие классические темы математических основ информатики: праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами. Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстно-свободными грамматиками.