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