Формальные языки 2015 — различия между версиями
Darnley (обсуждение | вклад) |
Darnley (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}: | 1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}: | ||
| − | a) множество слов, содержащих подстроку | + | a) множество слов, содержащих подстроку «011»; |
| − | b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на | + | b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»; |
c) множество слов, в которых нет пяти одинаковых цифр подряд. | c) множество слов, в которых нет пяти одинаковых цифр подряд. | ||
| Строка 32: | Строка 32: | ||
a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3; | a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3; | ||
| − | b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек | + | b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»; |
| − | c) множество слов, в которых на одной из трех левых или двух правых позиций стоит | + | c) множество слов, в которых на одной из трех левых или двух правых позиций стоит единица; |
3) Детерминизируйте автомат, являющийся ответом на задание 2b. | 3) Детерминизируйте автомат, являющийся ответом на задание 2b. | ||
Версия 02:02, 24 февраля 2015
Лектор — Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика — Михаил Эдуардович Дворкин
Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное невозможность описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
- Правые контексты.
Лекция 2
- Динамическое программирование по ДКА.
- Прямое произведение ДКА.
- Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
- Детерминизация НКА.
Д/з №1, срок сдачи: 3 марта 2015 г., 14:10
1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:
a) множество слов, содержащих подстроку «011»;
b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»;
c) множество слов, в которых нет пяти одинаковых цифр подряд.
2) Опишите HКА или ε-НКА, который распознает следующее множество слов над алфавитом {0, 1}:
a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;
b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»;
c) множество слов, в которых на одной из трех левых или двух правых позиций стоит единица;
3) Детерминизируйте автомат, являющийся ответом на задание 2b.
4) ... и минимизируйте результат выполнения задания 3.
