Alexander Sayapin Teacher's site

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

Posted on Tue 09 February 2021

In Архив.

tags: дискретная математика мит


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

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

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

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

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

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

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

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

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

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

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

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

  1. Формальные языки, грамматики и автоматы. Язык, строка, алфавит. Основные понятия.

  2. Формальные языки. Понятие формальной грамматики.

  3. Формальная грамматика. Вывод (цепочка вывода). Вывод, непосредственный вывод, отношение выводимости, язык, порождаемый грамматикой

  4. Формальная грамматика. Классификация грамматик. Примеры грамматик.

  5. Формальная грамматика. Вывод в КС-грамматиках и правила построения дерева вывода. Синтаксический разбор, левый и правый вывод.

  6. Формальная грамматика. Неоднозначные грамматики. Неоднозначные и эквивалентные грамматики.

  7. Формальные языки и грамматики. Рекурсия в языке. Рекурсивные правила, их классификация.

  8. Формальные языки и грамматики. Способы описания правил в грамматиках. БНФ и РБНФ.

  9. Формальные языки, грамматики и автоматы. Регулярный язык и его особенности.

  10. Формальная грамматика. Способы описания правил в грамматиках. Синтаксическая диаграмма. как способ описания грамматики.

  11. Автоматные грамматики и конечные автоматы. Распознаватель.

  12. Конечные автоматы. Детерминированные и недетерминированные конечные автоматы.

  13. Детерминированные и недетерминированные конечные автоматы. Преобразования автоматов. Эквивалентные состояния и автоматы. Минимизация конечного автомата.

  14. Теория автоматов. Связь недетерминированных и детерминированных автоматов. Переход из НКА без переходов по пустой строке в ДКА.

  15. Теория автоматов. Конечные автоматы. Синтез и анализ конечного автомата. Преобразование регулярной грамматики в конечный автомат. Примеры.

  16. Теория автоматов. Автоматы с магазинной памятью. Их связь с КС-грамматиками.

  17. Теория автоматов. Формальные языки, грамматики и автоматы. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ.

  18. Теория автоматов. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ. LL(1)-грамматика.

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

tags

алфавит (1) asp.net (1) бгд (22) бисв (22) бкб (22) бме (22) бпэ (23) бпэз (3) бпэзу (1) бпм (13) бпм объявления (7) certbot (1) cheatsheet (1) checkinstall (1) csv (1) дискретная математика (21) экзамен (1) embedded rust (2) english (1) формальные грамматики (1) gdb (2) язык (1) jupyter (1) критерии (2) курсовая работа (2) lighttpd (2) low-latency (1) machine learning (3) make (1) make install (1) markdown (1) машинное обучение (1) математическая логика (1) Математические основы кмпьютерной графики (1) Математические основы компьютерного моделирования (1) Методы оптимизации (9) методы оптмимизации (1) методы принятия решений (1) миа (1) мии (7) мик (7) мим (2) мип (8) мит (34) миу (8) миз (7) ml (1) mono (1) natural language processing (1) nlp (1) nucleo (2) объявления (28) оформление (2) openocd (2) openpgp (1) pandas (1) pgp (1) подтверждение вывода (1) programming (3) python (3) robot (1) robotics (2) setup (6) шпаргалка (1) smartcard (1) ssh (1) ssl (1) STM32 (2) streaming (1) строка (1) тб (21) teaching (1) teaching statement (1) теоретические основы цифровой обработки изображений (1) тест (1) учебник (1) up board (1) video (1) вкр (2) xls (1)