Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Теория формальных языков

Спецкурс читает М. Р. Пентус. Курс рассчитан на студентов 1—6-го курсов.

Программа спецкурса: детерминизация конечного автомата, свойства класса автоматных языков, лемма о разрастании для автоматных языков, преобразование конечного автомата в регулярное выражение, минимизация детерминированных конечных автоматов, лемма о разрастании для контекстно-свободных языков, свойства класса контекстно-свободных языков, преобразование автомата с магазинной памятью в контекстно-свободную грамматику, неразрешимость проблемы соответствий Поста, неразрешимые проблемы про контекстно-свободные грамматики.