Алгебраические и логические методы в компьютерных науках

Последнее изменение: 07/05/2015 20:00:00

Обязательный курс для 1-го курса магистратуры-КН. Рекомендуется как специальный курс для 1-го курса магистратуры-МТ и ФИИТ и для студентов старших курсов бакалавриата. В весеннем семестре 2014/15 учебного года читается по понедельникам с 14:30.

Литература для дополнительного чтения

  • Jean-Éric Pin. Varieties of formal languages. North Oxford, London & Plenum, New-York, 1986.
  • Howard Straubing. Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA, 1994.

Краткое содержание курса

  • Алгебраическая теория формальных языков
    • Теоремы Щютценберже и Саймона
    • Теория Эйленберга и ее современные обобщения
  • Логическая теория формальных языков
    • Монадическая логика второго порядка. Результаты Бюхи
    • Теорема Макнотона

Вопросы к экзамену по итогам весеннего семестра

  1. Логика первого порядка. Монадическая логика второго порядка. Задание языков формулами первого и второго порядка.
  2. Теорема Бюхи о логической характеризации регулярных языков. Доказательство необходимости условия теоремы Бюхи (язык, распознаваемый конечным автоматом, задается формулой монадической логики второго порядка).
  3. V-слова и (V_1,V_2)-слова. Интерпретация формул первого и второго порядка, содержащих свободные переменные. Доказательство достаточности условия теоремы Бюхи (язык, задаваемой формулой монадической теории второго порядка, распознается конечным автоматом).
  4. Языки бесконечных слов. Распознаваемость языков бесконечных слов по Бюхи. Детерминированные и недетерминированные автоматы Бюхи.
  5. Теорема Бюхи для языков бесконечных слов. Доказательство необходимости условия теоремы Бюхи (язык, распознаваемый автоматом Бюхи, задается формулой монадической логики второго порядка).
  6. Характеризация языков бесконечных слов, распознаваемых автоматом Бюхи, через регулярные языки конечных слов.
  7. Теорема Рамсея (без доказательства). Замкнутость класса языков бесконечных слов, распознаваемых автоматом Бюхи, относительно дополнения. Доказательство достаточности условия теоремы Бюхи для языков бесконечных слов.
  8. Теорема Макнотона.

Задачи к экзамену

Смотрите также: