Формальные языки, 5 курс, 2 семестр, 2016/17

Лектор — Дворкин Михаил Эдуардович, mikhail.dvorkin@gmail.com

Практика — Михаил Слабодкин (slabodkinm@gmail.com), Екатерина Вербицкая

Лекции

Лекция 1

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

Лекция 2

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

Практика Слабодкин

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

Практика 1

Практика 2

Практика 3

Практика Вербицкая

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

Практика 1

Практика 2

Практика 3

Ссылки

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