Формальные языки 2015
Лектор — Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика — Михаил Эдуардович Дворкин
День зачёта
10:00—11:30 Тест. Письменный, решение задач на темы курса. В этой части пользоваться книгами и конспектами нельзя. Проверяться будет понимание, а не выучивание.
12:30 Объявление результатов теста. Варианты могут быть: получение зачёта, вытягивание 1 теорвопроса, вытягивание 2 теорвопросов.
12:30—... Подготовка теорвопросов, сдача их в порядке живой очереди. Можно пользоваться конспектом, книгами, интернетом.
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
- Правые контексты.
Лекция 2
- Динамическое программирование по ДКА.
- Прямое произведение ДКА.
- Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
- Детерминизация НКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики.
- Вывод, левосторонний вывод, дерево разбора.
- Однозначные КС-грамматики.
- Вложенность регулярных языков в КС-языки.
Лекция 6
- КС-грамматики с АРВ в правой части.
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Лекция 7
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью
Лекция 8
- Эквивалентность МП-автоматов и КС-грамматик
- Иерархия Хомского
Д/з №1, срок сдачи: 3 марта 2015 г., 14:10
В бумажном виде или (на большее число баллов) хорошо свёрстанное (LaTeX + tikz) по эл. почте с темой письма «SPbAU FL HW1 Your Name».
1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:
a) множество слов, содержащих подстроку «011»;
b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»;
c) множество слов, в которых нет пяти одинаковых цифр подряд.
2) Опишите HКА или ε-НКА, который распознает следующее множество слов над алфавитом {0, 1}:
a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;
b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»;
c) множество слов, в которых на хотя бы одной из трех левых или двух правых позиций стоит единица;
3) Детерминизируйте автомат, являющийся ответом на задание 2b.
4) ... и минимизируйте результат выполнения задания 3.
