Теоретическая информатика 3

Курс «теоретическая информатика-3», посвящённый теории автоматов, формальных грамматик и сложности вычислений, читается А. Охотиным осенью 2017 года студентам 2-го курса СПбГУ, обучающимся по программе «математика».

Лекции

  1. (4 сентября) Машины Тьюринга и неразрешимые задачи. Теорема Райса. Детерминированные конечные автоматы (DFA).
  2. (11 сентября) Формальные языки и действия над ними. Регулярные выражения. Недетерминированные конечные автоматы (NFA). Преобразование NFA к DFA (преобразование подмножеств). Нерегулярность языка {anbn | n>=0}.
  3. (18 сентября) Формальные языки и действия над ними. Преобразование регулярных выражений в ε-NFA, преобразование ε-NFA в NFA, преобразование NFA в регулярные выражения. Лемма о накачке для регулярных языков. DFA для пересечения, дополнения и поэлементного квадратного корня.

Задачи для самостоятельного решения («листочки»)

  1. Задачи по регулярным языкам, которые необходимо сдать до 13 октября.
«Листочки» можно сдавать А. С. Охотину или С. А. Пузыниной. Если студент начал сдавать задачу из листочка одному из преподавателей, но сдать её с первой попытки не получилось, то далее эту задачу следует сдавать тому же преподавателю. Разные задачи при желании можно сдавать разными преподавателям.
E-mail: