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

Материал из SEWiki
Перейти к: навигация, поиск
(Новая страница: « == Лекции == Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''') == Практика Слабо…»)
 
 
(не показаны 4 промежуточные версии 4 участников)
Строка 1: Строка 1:
  
 
== Лекции ==
 
== Лекции ==
−
Преподаватель: Дворкин Михаил Эдуардович ('''mikhail.dvorkin@gmail.com''')
+
Преподаватель: Дворкин Михаил Эдуардович (<code>mikhail.dvorkin@gmail.com</code>)
  
−
== Практика Слабодкин ==
 
  
−
Преподаватель: Слабодкин Михаил ('''slabodkinm@gmail.com ''')
+
==== Список билетов на экзамене ====
  
−
== Практика Вербицкая ==
+
# Детерминированные конечные автоматы. Принятие слова. Эквивалентность состояний. Минимизация ДКА.
 +
# Правые контексты. Прямое произведение ДКА. Динамическое программирование по ДКА.
 +
# Недетерминированные КА, их соотношение с детерминированными. Распознавание слова НКА. Детерминизация. Эквивалентность ДКА и НКА.
 +
# Академические регулярные выражения. Теорема Клини — эквивалентность КА и АРВ.
 +
# Лемма о разрастании для ДКА.
 +
# КС-грамматики. Вывод, левосторонний вывод, дерево разбора. Однозначные КС-грамматики.
 +
# Нормальная форма Хомского. Все этапы алгоритма приведения к НФХ.
 +
# Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
 +
# Лемма о разрастании для КС-грамматик.
 +
# Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию. Эквивалентность МП-автоматов и КС-грамматик.
 +
# Детерминированные автоматы с магазинной памятью, неэквивалентность двух видов приема. Соотношение регулярных, ДМП- и КС-языков.
 +
# Иерархия Хомского. Регулярные грамматики, эквивалентность ДКА. Неограниченные грамматики, эквивалентность машинам Тьюринга.
 +
# Контекстно-зависимые грамматики, неукорачивающие грамматики. Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней.
  
−
Преподаватель: Вербицкая Екатерина ('''kajigor@gmail.com''')
+
 
 +
==== Ссылки ====
 +
 
 +
 
 +
* Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
 +
* [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков neerc.ifmo.ru]
 +
* [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/]
 +
* [http://www.eecs.wsu.edu/~ananth/CptS317/]
 +
* [http://users.utu.fi/jkari/automata/fullnotes.pdf]
 +
* [http://yeputons.net/spbau/term4/formal_languages-lectures.pdf]
 +
 
 +
== Практика ==
 +
 
 +
=== Слабодкин Михаил ===
 +
 
 +
Контакты: <code>slabodkinm@gmail.com</code>
 +
 
 +
[https://docs.google.com/spreadsheets/d/1n6EkI7WZkAc9bNBnr4VtqxqOUodPaHn7A81qGjOzulc/edit?usp=sharing Таблица с результатами]
 +
 
 +
=== Вербицкая Екатерина ===
 +
 
 +
Контакты: <code>kajigor@gmail.com</code>
 +
 
 +
[https://docs.google.com/spreadsheets/d/1n6EkI7WZkAc9bNBnr4VtqxqOUodPaHn7A81qGjOzulc/edit#gid=111213337 Таблица с результатами]
 +
 
 +
[https://drive.google.com/drive/folders/1yBgcf2yIvxV7NTmm08nWBdu5GcqbeMh5 Домашние задания]
 +
 
 +
'''Важно''': префикс для темы писем с домашками: <code>[FL_SPbAU] HWxx</code>

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

Лекции

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


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

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


Ссылки

  • Важная книга: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
  • neerc.ifmo.ru
  • [1]
  • [2]
  • [3]
  • [4]

Практика

Слабодкин Михаил

Контакты: slabodkinm@gmail.com

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

Вербицкая Екатерина

Контакты: kajigor@gmail.com

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

Домашние задания

Важно: префикс для темы писем с домашками: [FL_SPbAU] HWxx

Источник — «http://mit.spbau.ru/sewiki/index.php?title=Формальные_языки_5SE_весна_2018&oldid=15835»