Семинар 28.05 Подгруппа 106-2 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(Новая страница: «В качестве допуска к контесту необходимо решить хотя бы одну задачу из каждой группы. По-…») |
|||
Строка 1: | Строка 1: | ||
− | В качестве допуска к контесту необходимо решить хотя бы одну задачу из каждой группы. | + | В качестве допуска к контесту 4 необходимо до 2 июня решить хотя бы одну задачу из каждой группы. |
По-хорошему, надо прорешать все, они несложные. | По-хорошему, надо прорешать все, они несложные. | ||
Текущая версия на 02:50, 1 июня 2015
В качестве допуска к контесту 4 необходимо до 2 июня решить хотя бы одну задачу из каждой группы. По-хорошему, надо прорешать все, они несложные.
1. Построить ДКА по НКА
- Для каждого из автоматов https://yadi.sk/d/fNAHbjCZghERG постройте соответствующий ему ДКА.
Для допуска нужно это сделать для любого из автоматов, кроме первого.
2. Написать регулярные выражения
- Напишите регулярное выражение для языка над алфавитом Σ = {0, 1} каждое слово которого содержит хотя бы два нуля.
- Напишите регулярное выражение над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5.
- Напишите регулярное выражение для языка над алфавитом Σ = {0, 1, 2, 3}, состоящий из слов, в которых хотя бы одна из последних пяти букв является 1
3. КА и регулярные выражения
- Постройте конечный автомат для языка (111 U 01)*1(00 U 11)*.
- Постройте конечный автомат для языка (ab)*(a U b)(b U a)*(a U bab).
4 Использование леммы о накачке
- Докажите, что не существует КА, который бы читал язык {0n1n2n}. (Пояснение: запись 0n означает строку из n нулей: 00...0.)
- Докажите, что не существует КА, который бы читал язык {0n1n}.
- Докажите, что не существует КА, который бы читал язык {0n!}.