• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Теория автоматов и формальных языков

2018/2019
Учебный год
RUS
Обучение ведется на русском языке
3
Кредиты

Программа дисциплины

Аннотация

В рамках курса студенты изучают актуальные разделы теоретической информатики: теорию автоматов и формальных языков, теорию вычислимости и сложности вычислений. В результате прохождения учебного курса студенты должны знать способы задания формальных языков с помощью грамматик и автоматных моделей, классификацию формальных языков, разрешимость свойств формальных языков, классы вычислительной сложности; иметь представление об использовании теории формальных языков в компьютерной лингвистике; о неразрешимых и труднорешаемых проблемах; уметь описывать формальные языки, переводить описания формальных языков из одной формы в другую, пользоваться теорией формальных языков для решения прикладных задач компьютерной лингвистики, оценивать задачи с точки зрения разрешимости и сложности.
Цель освоения дисциплины

Цель освоения дисциплины

  • Целью преподавания дисциплины “Теория автоматов и формальных языков” является изучение теории автоматов, формальных языков, основных понятий вычислимости и разрешимости, а также основ теории сложности вычислений.
Планируемые результаты обучения

Планируемые результаты обучения

  • Понятие формального языка. Примеры формальных языков. Студент знает принципы задания языка конечными автоматами и порождения языков формальными грамматиками. Имеет представление об операциях над языками.
  • Студент имеет представление о детерминированных и недетерминированных конечных автоматах, регулярных языках и регулярных выражениях. Знает свойства регулярных языков и лемму о накачке для регулярных языков и умеет её примененять. Знаком с линейными и автоматными грамматиками и их свойствами.
  • Студент имеет представление о контекстно-свободных грамматиках и языках, деревьях разбора, автоматах с магазинной памятью. Знаком со свойствами КС-языков, леммой о накачке для КС-языков и алгоритмом распознавания для КС-языков.
  • Студент знаком с грамматиками общего вида и рекурсивно перечислимыми языками, иерархией Хомского, рекурсивными языками. Имеет представление о задании РП и рекурсивных языков машиной Тьюринга и свойствах РП языков.
  • Имеет представление о диагональной конструкции Кантора и существовании не РП языков. Знаком с понятием алгоритмически разрешимой проблемы, примерами неразрешимых проблем, теоремой Райса.
  • Студент знаком с понятием сложность вычислений и классами сложности, умеет определять сложность алгоритмов
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Понятие формального языка. Способы задания формальных языков.
    Понятие формального языка. Примеры формальных языков. Задание языков конечными автоматами. Порождение языков формальными грамматиками. Операции над языками.
  • Регулярные языки: способы задания и свойства
    Детерминированные и недетерминированные конечные автоматы. Регулярные языки и регулярные выражения. Свойства регулярных языков. Лемма о накачке для регулярных языков и ее применение. Понятие вывода в формальной грамматике. Язык, порождаемый грамматикой. Линейные и автоматные грамматики и их свойства. Эквивалентность автоматных грамматик и конечных автоматов.
  • Контекстно-свободные языки: способы задания и свойства
    Контекстно-свободные грамматики (КС-грамматики) и контекстно-свободные языки (КС-языки). Деревья разбора. Автоматы с магазинной памятью (МП-автоматы). Эквивалентность МП-автоматов и КС-грамматик. Свойства КС-языков. Лемма о накачке для КС-языков. Алгоритм распознавания для КС-языков.
  • Рекурсивные и рекурсивно перечислимые языки
    Грамматики общего вида и рекурсивно перечислимые языки (РП языки). Иерархия Хомского. Рекурсивные языки. Задание РП и рекурсивных языков машиной Тьюринга. Свойства РП языков.
  • Рекурсивно неперечислимые языки и алгоритмическая разрешимость
    Диагональная конструкция Кантора и существование не РП языков. Понятие алгоритмически разрешимой проблемы. Примеры неразрешимых проблем. Теорема Райса.
  • Сложность вычислений. Классы сложности
Элементы контроля

Элементы контроля

  • неблокирующий контрольная работа
  • неблокирующий контрольное домашнее задание
  • неблокирующий Экзамен
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.2 * контрольная работа + 0.2 * контрольное домашнее задание + 0.6 * Экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • Князьков В.С., Волченская Т.В. - Введение в теорию автоматов - Национальный Открытый Университет "ИНТУИТ" - 2016 - 89с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100715

Рекомендуемая дополнительная литература

  • Алымова, Е. В. Конечные автоматы и формальные языки : учебник / Е. В. Алымова. В. М. Деундяк. А. М. Пеленнцын ; Южный федеральный университет. - Ростов-на-Дону : Таганрог : Издательство Южного федерального университета. 2018. - 292 с. - ISBN 978-5-9275-2397-9. - Текст : электронный. - URL: https://new.znanium.com/catalog/product/1020503 - Текст : электронный. - URL: http://znanium.com/catalog/product/1020503