Семинар 28.05 Подгруппа 106-2

В качестве допуска к контесту 4 необходимо до 2 июня решить хотя бы одну задачу из каждой группы. По-хорошему, надо прорешать все, они несложные.

1. Построить ДКА по НКА

1. Для каждого из автоматов https://yadi.sk/d/fNAHbjCZghERG постройте соответствующий ему ДКА.

Для допуска нужно это сделать для любого из автоматов, кроме первого.

2. Написать регулярные выражения

1. Напишите регулярное выражение для языка над алфавитом Σ = {0, 1} каждое слово которого содержит хотя бы два нуля.
2. Напишите регулярное выражение над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5.
3. Напишите регулярное выражение для языка над алфавитом Σ = {0, 1, 2, 3}, состоящий из слов, в которых хотя бы одна из последних пяти букв является 1

3. КА и регулярные выражения

1. Постройте конечный автомат для языка (111 U 01)^*1(00 U 11)^*.
2. Постройте конечный автомат для языка (ab)^*(a U b)(b U a)^*(a U bab).

4 Использование леммы о накачке

1. Докажите, что не существует КА, который бы читал язык {0ⁿ1ⁿ2ⁿ}. (Пояснение: запись 0ⁿ означает строку из n нулей: 00...0.)
2. Докажите, что не существует КА, который бы читал язык {0ⁿ1ⁿ}.
3. Докажите, что не существует КА, который бы читал язык {0^n!}.