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