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

2018/2019

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс по выбору

Когда читается:

3-й курс, 3, 4 модуль

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

Аннотация

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

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

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

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

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

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

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

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

• контрольная работа
• контрольное домашнее задание
• Экзамен

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

• Промежуточная аттестация (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