ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

Аннотация

Данное пособие представляет собой семестровый курс для студентов, обучающихся по математическим специальностям. Основная цель настоящего курса – ознакомить обучающихся с основными терминами и понятиями теории формальных языков и подготовить их к дальнейшему знакомству с теорией сложности, методами трансляции и обработки текстовой информации. В связи с этим рассматриваются базовые определения и теоремы, имеющие отношение к данной тематике. Затрагиваются такие формализмы, связанные с определением языков, как системы текстовых замен, грамматики, автоматы, регулярные выражения. Большое внимание уделяется рассмотрению регулярных и контекстно-свободных языков.