Описание:Задание языков с помощью формальных гармматик. Иерархия Хомского, контекстно зависимые и контекстно свободные грамматики, право- и леволинейные грамматики. Конечные автоматы и автоматные языки. Эквивалениность недетерминированных и детерминированных конечных автоматов, алгоритм построения минимального детерминированного конечного автомата. Совпадение классов автоматных языков и языков, порожденных право- и леволинейными грамматиками. Регулярные языки и выражения. Теорема Клини о совпадении классов автоматных и регулярных языков. Операции над автоматными и контекстно свободными языками. Алгоритмические проблемы теории формальных языков.
Задача разбора для контекстно свободных языков. Нисходящий (рекурсивный) разбор, понятие хвостовой рекурсии. Восходящий разбор (LR-разбор, или разбор с помощью конечного автомата со стеком). Практическая реализация задачи разбора на языке C++.