Формальные языки, 2 курс, весна 2016

Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)

Практика: Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа).

План

Лекция 1

• Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
• Детерминированные конечные автоматы. Принятие слова.
• Эквивалентность состояний. Минимизация ДКА.

Лекция 2

• Правые контексты.
• Эквивалентность ДКА.
• Прямое произведение ДКА.
• Динамическое программирование по ДКА.

К занятиям Николая Карпова

Все материалы и табличка.

Таблица с результатами

Домашние задания

Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.

№	Дата
1	На 19.02.2016
2	На 26.02.2016
3	На 04.03.2016
4	На 11.03.2016
5	На 18.03.2016
6	На 25.03.2016
7	На 01.04.2016

К занятиям Михаила Слабодкина

Результаты

Ссылки

• Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
• [1]
• [2]
• [3]
• [4]