Общее
Формирование способностей использования формальных языков для решения задач в различных областях.
Получить навыки анализа формальных языков.
Использование методов решения задач из области формальных языков.
Тематический план
ТЕМА 1: Основные понятия: алфавит, цепочка, язык. Способы определения формальных языков. Примеры
Знакомство с кросплатформенной программой JFLAP. Регулярные языки
Примеры формальных грамматик и языков в соответствии классификации Хомского
ТЕМА 2: Формальные грамматики и языки по классификации Хомского
Примеры формальных грамматик и языков в соответствии классификации Хомского
ТЕМА 3: Регулярная грамматика и конечные автоматы. Определения, примеры
Знакомство с JFLAP кросплатформенной программой. Регулярные языки
ТЕМА 4: Графическое представление конечного автомата. Детерминированный и недетерминированный конечный автомат. Алгоритм построения детерминированного автомата эквивалентного недетерминированному
Эквивалентное преобразование недетерминированного конечного автомата в детерминированный. Примеры
ТЕМА 5 : Эквивалентность регулярной грамматики и конечного автомата. Теорема GF.
Конечные автоматы.
Эквивалентное преобразование регулярной грамматики в конечный автомат. Теорема GF. Примеры
ТЕМА 6: Эквивалентность конечного автомата и регулярной грамматики. Теорема FG.
Эквивалентное преобразование конечного автомата и регулярной грамматики. Теорема FG. Примеры
ТЕМА 14: Нормальная форма Грейбаха
Нормальная форма Хомского
ТЕМА 16: Проектирование лексического анализатора
LAB 4 LFA
Нормальная форма Грейбаха
ТЕМА 17: Автоматы с магазинной памятью. Зеркальный язык
Автомат с магазинной памятью. Примеры
ТЕМА 21: Синтаксический анализатор на основе LL (1) грамматики
LAB 5(2) LFA
Нисходящий синтаксический анализаторНисходящий синтаксический анализ на основе LL (1) грамматики. Примеры
ТЕМА 22: Алгоритм эквивалентного преобразования грамматики с исключением общего префикса
Нисходящий синтаксический анализ на основе LL (1) грамматики. Примеры