Формальные языки 2015
Лектор — Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика — Михаил Эдуардович Дворкин
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
- Правые контексты.
Лекция 2
- Динамическое программирование по ДКА.
- Прямое произведение ДКА.
- Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
- Детерминизация НКА.
Лекция 3
- Академические регулярные выражения.
- Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
- Операции над языками. Свойства регулярных языков.
- Лемма о разрастании.
Лекция 5
- КС-грамматики
- Вывод, левосторонний вывод, дерево разбора
- Однозначные КС-грамматики
- Вложенность регулярных языков в КС-языки
Лекция 6
- Нормальная форма Хомского.
- Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
- Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Д/з №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.
