Формальные языки 2MIT весна 2018 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Практика Слабодкин)
(Список билетов на экзамене)
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
 
== Лекции ==
 
== Лекции ==
 
Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''')
 
Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''')
 +
 +
== Список билетов на экзамене ==
 +
 +
# Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
 +
# Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
 +
# Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
 +
# Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
 +
# Лемма о разрастании для ДКА.
 +
# КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
 +
# Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
 +
# Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
 +
# Лемма о разрастании для КС-грамматик.
 +
# Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
 +
# Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
 +
# Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
 +
# Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.
  
 
== Практика Слабодкин ==
 
== Практика Слабодкин ==
Строка 13: Строка 28:
 
* [[Медиа:FL3_spring2018.pdf | Задания к практике №3]]
 
* [[Медиа:FL3_spring2018.pdf | Задания к практике №3]]
 
* [[Медиа:FL4_spring2018.pdf | Задания к практике №4]]
 
* [[Медиа:FL4_spring2018.pdf | Задания к практике №4]]
 +
* [[Медиа:FL5_spring2018.pdf | Задания к практике №5]]
 +
* [[Медиа:FL6_spring2018.pdf | Задания к практике №6]]
 +
* [[Медиа:FL7_spring2018.pdf | Задание к практике №7]]
  
 
== Практика Вербицкая ==
 
== Практика Вербицкая ==
Строка 24: Строка 42:
 
[https://docs.google.com/spreadsheets/d/1I-UG1UHBldLlC0EwRRlbyVJJKvVqH5X6VHMMueEYYM0/ Таблица с результатами]
 
[https://docs.google.com/spreadsheets/d/1I-UG1UHBldLlC0EwRRlbyVJJKvVqH5X6VHMMueEYYM0/ Таблица с результатами]
  
Задание: см. Практика Слабодкин
+
[http://mit.spbau.ru/sewiki/images/9/98/Fl.pdf Все задания]

Текущая версия на 12:31, 18 июня 2018

Лекции

Преподаватель: Дворкин Михаил Эдуардович (mikhail.dvorkin@gmail.com)

Список билетов на экзамене

  1. Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
  2. Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
  3. Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
  4. Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
  5. Лемма о разрастании для ДКА.
  6. КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
  7. Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
  8. Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
  9. Лемма о разрастании для КС-грамматик.
  10. Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
  11. Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
  12. Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
  13. Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.

Практика Слабодкин

Преподаватель: Слабодкин Михаил Григорьевич(slabodkinm@gmail.com )

Таблица с результатами

Практика Вербицкая

Преподаватель: Вербицкая Екатерина Андреевна (kajigor@gmail.com)

Практика Палецких

Преподаватель: Палецких Алексей Андреевич (a.paletskikh@gmail.com)

Таблица с результатами

Все задания