Документ взят из кэша поисковой машины. Адрес оригинального документа : http://oit.cmc.msu.ru/lectures/Tasks.doc Дата изменения: Tue Dec 10 16:08:20 2002 Дата индексирования: Mon Oct 1 20:10:30 2012 Кодировка: koi8-r

Задачи к курсу «Тестирование конформности и формальные языки»

1. Показать, что экземпляр PCP, заданный списками (a2b, a) и (a2, ba2), не
имеет решения.
2. Упр.1, п.3.2, Language.ps
3. Упр.2, п.3.2, Language.ps
4. Пусть ? = {a, b, c} - трехбуквенный алфавит. Найти тестовое множество
для языка L(?) = {ancbn | n>0}. Требуется не просто предъявить множество,
но и доказать, что оно действительно является тестовым.