Теория автоматов для МИТ20-01 / весна 2021

Posted on Tue 09 February 2021

Курс теории автоматов рассчитан на 1 семестр, в конце курса предусмотрен экзамен.

Итоговая оценка выставляется в соответствии с требованиями балльно-рейтинговой системы (см. критерии оценки на экзамене). Для допуска к экзамену необходимо выполнить и защитить все практические работы (ориентировочно 12 штук) и получить не менее 51 балла в течение семестра.

Начать изучение курса можно с неформального введения в формальные грамматики.

Список заданий:

Формальные грамматики. При выполнении работы можно использовать следующие материалы: текст по формальным грамматикам, Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 77, В.С. Фомичев Формальные языки, грамматики и автоматы[электр]. Для выполнения работы так же необходима программа JFLAP, так же доступная с этого сайта, для запуска необходима установленная на компьютере JAVA. Описание работы с программой имеется в методичке.
- Список адресов для самопроверки, допустимые:
  - a@a.a
  - aa@a.a
  - a@aaaa.a
  - a@a.aaaa
  - a.a@a.a
  - a.a@a.a.a
  - a.a.a@a.a
  - a@a.aa.a
  - a@aa.aa.aa
- Список адресов для самопроверки, недопустимые:
  - a
  - aa
  - a@
  - @a
  - a@a
  - a@a.
  - a@.a
  - a@a.
  - a.@a.a
  - .a@a.a
  - a..a@a.a
  - a.a@a..a
  - a.a@a.a.a.
- Список так же доступен в виде файла, можно использовать для проверки в JFLAP, выбрав в меню пункты Input/Multiple Brute Force Parse, и нажав кнопку Load Inputs. Учтите, проверка потребует времени, поскольку производится методом брутфорса (фактически, полного перебора всех правил с проверкой их применимости на каждом этапе разбора)
Классификация грамматик и их представления. При выполнении работы можно использовать следующие материалы: Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 86-88, В.С. Фомичев Формальные языки, грамматики и автоматы (1.3. Типы формальных грамматик, 1.4.1. Форма Бекуса-Наура, 1.4.3. Синтаксическая диаграмма)
Конечные автоматы-распознаватели. При выполнении работы можно использовать следующие материалы: Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 102-105., Дискретная математика: учебное пособие/ В.М. Пестриков, В.С.Дудкин, Г.А.Петров. - Санкт-Петербург: 2013, стр. 1-6.

Список заданий будет расширен.

Решение заданий вам необходимо прислать в виде ссылки на Google Docs.

Для этого вам необходимо:

Иметь учетную запись Google (например, почту на gmail).
Войти в учетную запись Google
Перейти по ссылке на задание, расположенной ниже
Нажать кнопку Создать копию
Выполнить задание непосредственно в браузере, записывая ответы в предназначенные для них ячейки
Нажать кнопку Настройки доступа и выбрать пункт Комментирование
В поле Введите имена или адреса эл. почты введите alstutor@gmail.com и нажмите кнопку Отправить

Если работа принята, в блокноте появится комментарий Принято, в противном случае будет указано, где именно имеются ошибки.

При изучении курса так же можно использовать следующую литературу:

При выполнении заданий можно использовать следующие источники:

Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010
Ф. А. Новиков Дискретная математика. 2-е изд. – С-Пб.: Питер, 2013 г.
Эвнин А. Ю. Дискретная математика. Конспект лекций. – Челябинск: ЮУрГУ, 1998.
В.С. Фомичев Формальные языки, грамматики и автоматы[электр].
Мозговой М.В. Программирование. Классика программирования: алгоритмы, языки, автоматы.- М.: Наука и техника, 2006.

Примерный список вопросов к экзамену (состав и количество вопросов могут быть откорректированы):

Формальные языки, грамматики и автоматы. Язык, строка, алфавит. Основные понятия.
Формальные языки. Понятие формальной грамматики.
Формальная грамматика. Вывод (цепочка вывода). Вывод, непосредственный вывод, отношение выводимости, язык, порождаемый грамматикой
Формальная грамматика. Классификация грамматик. Примеры грамматик.
Формальная грамматика. Вывод в КС-грамматиках и правила построения дерева вывода. Синтаксический разбор, левый и правый вывод.
Формальная грамматика. Неоднозначные грамматики. Неоднозначные и эквивалентные грамматики.
Формальные языки и грамматики. Рекурсия в языке. Рекурсивные правила, их классификация.
Формальные языки и грамматики. Способы описания правил в грамматиках. БНФ и РБНФ.
Формальные языки, грамматики и автоматы. Регулярный язык и его особенности.
Формальная грамматика. Способы описания правил в грамматиках. Синтаксическая диаграмма. как способ описания грамматики.
Автоматные грамматики и конечные автоматы. Распознаватель.
Конечные автоматы. Детерминированные и недетерминированные конечные автоматы.
Детерминированные и недетерминированные конечные автоматы. Преобразования автоматов. Эквивалентные состояния и автоматы. Минимизация конечного автомата.
Теория автоматов. Связь недетерминированных и детерминированных автоматов. Переход из НКА без переходов по пустой строке в ДКА.
Теория автоматов. Конечные автоматы. Синтез и анализ конечного автомата. Преобразование регулярной грамматики в конечный автомат. Примеры.
Теория автоматов. Автоматы с магазинной памятью. Их связь с КС-грамматиками.
Теория автоматов. Формальные языки, грамматики и автоматы. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ.
Теория автоматов. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ. LL(1)-грамматика.

По всем вопросам можно писать на электронную почту (ссылка mail me справа).

Alexander Sayapin Teacher's site

Теория автоматов для МИТ20-01 / весна 2021

disciplines

links

social

tags