Семинар 28.05 Подгруппа 106-2
Материал из Wiki - Факультет компьютерных наук
Версия от 02:50, 1 июня 2015; Annaveronika (обсуждение | вклад)
В качестве допуска к контесту 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!}.