Задача 1. Слово называется слабо симметричным, если его можно преобразовать в симметричное некоторой последовательностью операций обращения, применяемых к произвольным подсловам получающихся слов. Определить, является ли слабо симметричным заданное слово.
Задача 2. Задана грамматика G, каждое правило которой имеет вид А->ВС или А->а, где А, В, С-нетерминалы, а a-терминал. Определить, выводимо ли заданное слово, составленное из терминалов, в грамматике G.
Задача 5. Нетерминал грамматики называется бесплодным, если из него нельзя вывести ни одного слова в алфавите терминалов. Найти все бесплодные нетерминалы заданной грамматики.
Задача 6. Правило грамматики G называется бесполезным, если его нельзя применить ни в одном выводе слов грамматики G. Найти и удалить все бесполезные правила заданной грамматики.
Задача 7. В заданной грамматике найти все нетерминалы А, удовлетворяющие следующему условию: из А выводимо слово длиной больше 1, содержащее нетерминал А.
Задача 8. Говорят, что нетерминал А грамматики G зависит от (терминального или нетерминального) символа s, если из А в G выводимо слово, содержащее вхождение символа s. Для заданной грамматики указать все символы каждого нетерминала, от которых он зависит.
Задача 9. Построить слово длиной n из букв A, В, С такое, чтобы всякие два его стоящих друг за другом полслова были различны. Известно, что для любого n существует хотя бы одно такое слово.
Задача 10. Пусть R - множество всех восьмибуквенных слов в алфавите A, В, С, D, в каждое из которых каждая буква входит по два раза. Определим две операции над такими словами: обращение и циклическую замену букв, не выводящую за пределы R (например, a-> b, b->a или а->с, с->b,b->а). Найти максимальное подмножество таких слов из R, что ни одно из них нельзя получить из другого путем применения указанных операций конечное число раз.
Задача 11. Слова v и w заданного множества слов L назовем взаимозаменяемыми, если для любых двух слов х и у (не обязательно из L) xvy? L < xwy I L. Найти все пары взаимозаменяемых слов из L.
Задача 12. По заданному слову определить какое-нибудь из его подслов, которое входит в него наибольшее число раз (например, подслово "око" входит в слово "рококо" два раза).
Задача 14. Задано множество правил подстановки вида Vi->Wi, где все Vi ,wi(1<=i<=n)-слова одной и той же длины. Определить, можно ли перевести слово v в слово w последовательным применением заданных правил подстановки. Например, если имеются правила подстановки ba->ab, cb->bc, са->ас, то слово сbbа переводится в слово abbc следующим образом: сbbа->cbab->cabb-> acbb->abcb->abbc.
Задача 16. Пусть W1, .... Wn - m- буквенные слова в некотором алфавите, a si (i=1, ..., m)-буква, которая наиболее часто встречается в i-й позиции слов wi, ..., Wn. Выбрать такое слово из заданного списка слов wi,:,Wn, которое отличается от слова s1 s2... sm в наименьшем числе позиций.
Задача 17. Грамматика называется праволинейной, если все ее правила имеют вид А->-аВ или С->b, где A, В, С-нетерминалы, а,b - терминалы- По двум заданным праволинейным грамматикам определить их эквивалентность.
Задача 18. Задана грамматика, в которой все правила имеют вид А->В или С->а, где A, B, С-нетерминалы, а-терминалы. По заданному подмножеству М терминальных символов определить минимальное множество нетерминалов, из которых можно вывести все терминалы из М.
Задача 19. Активной емкостью некоторого вывода в грамматике назовем максимум числа нетерминалов, встречающихся в каждом из промежуточных слов этого вывода. По заданным удлиняющей грамматике и слову найти вывод этого слова с минимальной активной емкостью.
Задача 20. По заданной грамматике построить такую, которая эквивалентна исходной, а каждое правило имеет вид A->ВС или А-> а, где A, В, С-нетерминалы, а-терминал.
Задача 23. Грамматика называется последовательностной, если ее нетерминалы можно упорядочить так (скажем, а1, А2, ..., An), что правила с левой частью Аi в правой части не содержат нетерминалов аi+1, Ai+2, ..., An (i=1,...,n). Определить, является ли последовательностной заданная грамматика.
Задача 24. Правило вывода в грамматике назовем заключительным, если в его правую часть входят только терминалы. Построить такой вывод заданного терминального слова в удлиняющей грамматике, в котором заключительные правила применяются только после всех незаключительных.
Задача 25. По заданной автоматной диаграмме D построить эквивалентную ей D' так, чтобы в D' было не более одной вершины такой, что все выходящие из нее дуги ведут к этой же вершине.
Задача 26. Две вершины в автоматной диаграмме называются близнецами, если выходящие из них дуги с одинаковыми пометками ведут к одной и той же вершине. По диаграмме D построить эквивалентную ей диаграмму D' так, чтобы в D' не было ни одной пары вершин-близнецов.
Указание. Удалить вершины, недостижимые от начальной, и склеить все склеиваемые вершины в каждой из диаграмм. Если полученные диаграммы совпадают, то исходные были эквивалентны, иначе - нет.
Задача 31. По двум заданным автоматным диаграммам D1, D2 определить, имеется ли в пересечении их языков L(D1)C L(D2} хотя бы одно слово заданной длины.
Задача 34. По заданной автоматной диаграмме построить такую эквивалентную автоматную диаграмму, в которой нет ни одной пары различных склеиваемых вершин.
