https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80_28.05_%D0%9F%D0%BE%D0%B4%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_106-2Семинар 28.05 Подгруппа 106-2 - История изменений2026-06-06T14:45:50ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80_28.05_%D0%9F%D0%BE%D0%B4%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_106-2&diff=1770&oldid=previmported>Annaveronika: Migrated current public revision from wiki.cs.hse.ru2015-05-31T23:50:46Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>В качестве допуска к контесту 4 необходимо до 2 июня решить хотя бы одну задачу из каждой группы.<br />
По-хорошему, надо прорешать все, они несложные.<br />
<br />
'''1. Построить ДКА по НКА'''<br />
# Для каждого из автоматов https://yadi.sk/d/fNAHbjCZghERG постройте соответствующий ему ДКА.<br />
Для допуска нужно это сделать для любого из автоматов, кроме первого.<br />
<br />
'''2. Написать регулярные выражения'''<br />
# Напишите регулярное выражение для языка над алфавитом Σ = {0, 1} каждое слово которого содержит хотя бы два нуля.<br />
# Напишите регулярное выражение над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5.<br />
# Напишите регулярное выражение для языка над алфавитом Σ = {0, 1, 2, 3}, состоящий из слов, в которых хотя бы одна из последних пяти букв является 1<br />
<br />
'''3. КА и регулярные выражения'''<br />
# Постройте конечный автомат для языка (111 U 01)<sup>*</sup>1(00 U 11)<sup>*</sup>.<br />
# Постройте конечный автомат для языка (ab)<sup>*</sup>(a U b)(b U a)<sup>*</sup>(a U bab).<br />
<br />
'''4 Использование леммы о накачке'''<br />
# Докажите, что не существует КА, который бы читал язык {0<sup>n</sup>1<sup>n</sup>2<sup>n</sup>}. (Пояснение: запись 0<sup>n</sup> означает строку из n нулей: 00...0.)<br />
# Докажите, что не существует КА, который бы читал язык {0<sup>n</sup>1<sup>n</sup>}.<br />
# Докажите, что не существует КА, который бы читал язык {0<sup>n!</sup>}.</div>imported>Annaveronika