В сборнике приведены задачи по основным темам курса “Автоматы и формальные языки”, читаемого для студентов Института информационных технологий и управления (ИИТУ) Санкт-Петербургского государственного политехнического университета. Сборник включает как тренировочные упражнения, позволяющие студентам проверить на практике знание теоретических вопросов курса (например, алгоритмов преобразования недетерминированного автомата в эквивалентный детерминированный автомат, алгоритмов стандартных методов синтаксического анализа, вопросов использования атрибутной семантики при компиляции фрагментов языков высокого уровня и т. п.), так и проблемные задачи, направленные на формирование у студентов понимания основных идей и методов трансляции, использования формальных языков для решения различных практических задач обработки текстов.

Печатается по решению Совета по издательской деятельности Ученого совета Санкт-Петербургского политехнического университета Петра Великого.

• ОГЛАВЛЕНИЕ
• Предисловие
• 1. Конечные автоматы — распознаватели формальных языков
• 2. Регулярные множества, регулярные выражения и автоматныеязыки
• 3. Иерархия Хомского порождающих грамматик и языков
• 4. Иерархия распознающих автоматов для порождающих грамматикХомского
• 5. Другие модели задания формальных языков
• 6. Язык Милан и стековая машина
• 7. Неоднозначные КС-п>амматики и атрибутные трансляции
• 8. Распознаватели подклассов КС-языков
• 9. Трансляция конструкций языков программирования