Это полугодовой спецкурс по выбору кафедры на механико-математическом факультете МГУ. Лекции проходят по пятницам в 15:00-16:35 в аудитории 13-27. Первая лекция состоялась 13 марта 2020 г.

Прошедшие лекции

• Лекция 1. КС-языки (13.03.2020)Скрыть

  • 1.1. Формальные языки
  • 1.4. Порождающие грамматики
  • 1.5. Классы грамматик
  • 7.1. Деревья вывода
  • 8.2. Устранение ε-правил
  • 8.3. Нормальная форма Хомского

  Домашнее задание (до 21.03.2020):
  (1) Устранить ε-правила в грамматике S->ε, S->aSbS.
  (2) Привести к нормальной форме Хомского грамматику F->ab, F->aFb, F->FF.
  (3) Эквивалентны ли грамматики из ответов первой и второй задачи?

• Лекции 2-3. Нормальная форма Грейбах (20-27.03.2020)

  • 8.4. Нормальная форма Грейбах

  Домашнее задание из учебника 2006 года (до 03.04.2020):
  (1) 8.4.8
  (2) 8.4.9
  (3) 8.4.10

• Лекции 4-5. Лемма о разрастании (03-10.04.2020)

  • 9.1. Лемма о разрастании для контекстно-свободных языков
  • 9.3. Свойства замкнутости класса линейных языков
  • 9.4. Свойства замкнутости класса контекстно-свободных языков

  Домашнее задание из задачника 2016 года (до 16.04.2020):
  4.1.2, 4.1.3, 4.1.6, 4.1.11, 4.1.13, 4.3.22, 4.3.23, 4.3.25, 4.3.27, 4.3.28, 4.3.32, 4.3.33, 4.3.34, 4.3.35, 4.4.3.

• Лекция 6. Пересечение и дополнение КС-языков (17.04.2020)

  • 9.5. Пересечение и дополнение контекстно-свободных языков
  • 9.6. Пересечение контекстно-свободного языка с автоматным языком

  Домашнее задание из задачника 2016 года (до 23.04.2020):
  4.1.8, 4.1.12, 4.1.18, 4.1.19, 4.1.20, 4.1.33, 4.1.36, 4.5.2, 4.6.1, 4.6.10.

• Лекция 7. МП-автоматы (24.04.2020)

  • 10.1. Определение автомата с магазинной памятью

  Домашнее задание из задачника 2016 года (до 06.05.2020):
  5.1.7.

• Лекции 8-9. Эквивалентность МП-автоматов и КС-грамматик (08-15.05.2020)

  • 10.2. Характеризация контекстно-свободных языков

  Домашнее задание из задачника 2016 года (до 16.05.2020):
  5.2.17.

Основная литература

1. Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. -- М.: ИНТУИТ; БИНОМ. Лаборатория знаний, 2006. -- 247 с.
2. Пентус А. Е., Пентус М. Р. Контекстно-свободные языки [Электронный ресурс] : сборник задач. -- М.: РГГУ, 2016. -- 75 с.

Адрес: https://fervo.ru/mr/spec2020w.htm
Изменения внесены 27.04.2020.
Мати Рейнович Пентус